multiple values in #define(?) & counter placement

This is a discussion on multiple values in #define(?) & counter placement within the C Programming forums, part of the General Programming Boards category; Newbie needing help -- I am writing a program to implement sorting alogrithms and think what I have is correct ...

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    11

    multiple values in #define(?) & counter placement

    Newbie needing help -- I am writing a program to implement sorting alogrithms and think what I have is correct (feel free to double check me!). Where I am have problems is as part of the assignment the random input needs to be of sizes 300, 900, 1200, 2400, 6000, 9000, & 9900. I am currently using #define for the size of 300-- can I use the #define for multiple values? If so, what syntax for it? If not I am lost on what I need to do. Any suggestions? Also, to do an performance analysis on each algorithm I must implement a simple counter to increment by 1 unit in every iteration & measure the time taken by each algoritm. Can anyone help me on where to place the counters??
    Any assistance/suggestions would be appreciated. Thanks!


    Code:
     #include <stdlib.h>
    #include <stdio.h>
    
    #define NUM_ITEMS 300
    
    void insertionSort(int numbers[], int array_size);
    void heapSort(int numbers[], int array_size);
    void siftDown(int numbers[], int root, int bottom);
    void quickSort(int numbers[], int array_size);
    void q_sort(int numbers[], int left, int right);
    void mergeSort(int numbers[], int temp[], int array_size);
    void m_sort(int numbers[], int temp[], int left, int right);
    void merge(int numbers[], int temp[], int left, int mid, int right);
    
    int temp[NUM_ITEMS];
    int numbers[NUM_ITEMS];
    
    
    int main()
    {
      int i;
    
      //seed random number generator
      srand(getpid());
    
      //fill array with random integers
      for (i = 0; i < NUM_ITEMS; i++)
        numbers[i] = 1000 + rand()%24000;
    
      //perform insertion sort on array
      insertionSort(numbers, NUM_ITEMS);
    
      printf("Done with insertion sort.\n");
    
      heapSort(numbers, NUM_ITEMS);
    
      printf("Done with heap sort.\n");
    
      //perform quick sort on array
      quickSort(numbers, NUM_ITEMS);
    
      printf("Done with quick sort.\n");
    
    //perform merge sort on array
      mergeSort(numbers, temp, NUM_ITEMS);
    
      printf("Done with merge sort.\n");
    
    
       for (i = 0; i < NUM_ITEMS; i++)
        printf("%i\n", numbers[i]);
      
    
    }
    
    
    void insertionSort(int numbers[], int array_size)
    {
      int i, j, index, counter;
      counter = 0;
     
      for (i=1; i < array_size; i++)
      {
        index = numbers[i];
        j = i;
        while ((j > 0) && (numbers[j-1] > index))
        {
    	  counter++;
          numbers[j] = numbers[j-1];
          j = j - 1;
        }
        numbers[j] = index;
    	
      }
    printf("insertion sort counter= %i \n",counter);
    }
    
    
    
    void heapSort(int numbers[], int array_size)
    {
      int i, temp;
      for (i = (array_size / 2)-1; i >= 0; i--)
        siftDown(numbers, i, array_size);
    
      for (i = array_size-1; i >= 1; i--)
      {
        temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        siftDown(numbers, 0, i-1);
      }
    }
    
    
    void siftDown(int numbers[], int root, int bottom)
    {
      int done, maxChild, temp;
        
      done = 0;
      while ((root*2 <= bottom) && (!done))
      { 
    
        if (root*2 == bottom)
          maxChild = root * 2;
        else if (numbers[root * 2] > numbers[root * 2 + 1])
          maxChild = root * 2;
        else
          maxChild = root * 2 + 1;
    
        if (numbers[root] < numbers[maxChild])
        {
          temp = numbers[root];
          numbers[root] = numbers[maxChild];
          numbers[maxChild] = temp;
          root = maxChild;
        }
        else
          done = 1;
      }
    
    }
    
    
    void quickSort(int numbers[], int array_size)
    { 
      q_sort(numbers, 0, array_size - 1);
    
    }
    
    
    
    void q_sort(int numbers[], int left, int right)
    {
      int pivot, l_hold, r_hold;
      l_hold = left;
      r_hold = right;
      pivot = numbers[left];
      while (left < right)
      {
     
        while ((numbers[right] >= pivot) && (left < right))
          right--;
        if (left != right)
        {
          numbers[left] = numbers[right];
          left++;
        }
        while ((numbers[left] <= pivot) && (left < right))
          left++;
        if (left != right)
        { 
          numbers[right] = numbers[left];
          right--;
        }
     
      }
      numbers[left] = pivot;
      pivot = left;
      left = l_hold;
      right = r_hold;
      if (left < pivot)
        q_sort(numbers, left, pivot-1);
      if (right > pivot)
        q_sort(numbers, pivot+1, right);
      
     
    }
    
    
    
    void mergeSort(int numbers[], int temp[], int array_size)
    {
      m_sort(numbers, temp, 0, array_size - 1);
    }
    
    
    
    void m_sort(int numbers[], int temp[], int left, int right)
    {
      int mid;
    
      if (right > left)
      {
        mid = (right + left) / 2;
        m_sort(numbers, temp, left, mid);
        m_sort(numbers, temp, mid+1, right);
    
        merge(numbers, temp, left, mid+1, right);
      }
    }
    
    
    void merge(int numbers[], int temp[], int left, int mid, int right)
    {
      int i, left_end, num_elements, tmp_pos;
    
      left_end = mid - 1;
      tmp_pos = left;
      num_elements = right - left + 1;
    
      while ((left <= left_end) && (mid <= right))
      {
        if (numbers[left] <= numbers[mid])
        {
          temp[tmp_pos] = numbers[left];
          tmp_pos = tmp_pos + 1;
          left = left +1;
        }
        else
        {
          temp[tmp_pos] = numbers[mid];
          tmp_pos = tmp_pos + 1;
          mid = mid + 1;
        }
      }
    
      while (left <= left_end)
      {
        temp[tmp_pos] = numbers[left];
        left = left + 1;
        tmp_pos = tmp_pos + 1;
      }
      while (mid <= right)
      {
        temp[tmp_pos] = numbers[mid];
        mid = mid + 1;
        tmp_pos = tmp_pos + 1;
      }
    
      for (i=0; i <= num_elements; i++)
      {
        numbers[right] = temp[right];
        right = right - 1;
      }
    }

  2. #2
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,903
    Code:
    int temp[NUM_ITEMS];
    int numbers[NUM_ITEMS];
    
    
    int main()
    {
      int i;
    
      //seed random number generator
      srand(getpid());
    
      //fill array with random integers
      for (i = 0; i < NUM_ITEMS; i++)
        numbers[i] = 1000 + rand()%24000;
    
      //perform insertion sort on array
      insertionSort(numbers, NUM_ITEMS);
    
      printf("Done with insertion sort.\n");
    
      heapSort(numbers, NUM_ITEMS);
    
      printf("Done with heap sort.\n");
    
      //perform quick sort on array
      quickSort(numbers, NUM_ITEMS);
    
      printf("Done with quick sort.\n");
    
    //perform merge sort on array
      mergeSort(numbers, temp, NUM_ITEMS);
    
      printf("Done with merge sort.\n");
    
    
       for (i = 0; i < NUM_ITEMS; i++)
        printf("%i\n", numbers[i]);
      
    
    }
    Look in to dynamic array allocation. Also look in to taking the code that you have used with the NUM_ITEMS variable and replacing NUM_ITEMS with an actual variable, such as:
    Code:
    int num_items;
    Which you could either set via user input or use a nifty array trick:
    Code:
    int testSizes[] = {300, 900, 1200 };
    for(int a=0;a<sizeof(testSizes)/sizeof(int);a++)
    {
      int num_items = testSizes[a];
    // .. All code from main goes here, replacing NUM_ITEMS with num_items
    }

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    95
    > Newbie needing help -- I am writing a program to implement sorting alogrithms and think what I have is correct (feel free to double check me!). Where I am have problems is as part of the assignment the random input needs to be of sizes 300, 900, 1200, 2400, 6000, 9000, & 9900.

    Those are too small values ( like 9900).

    I used the function time. To measure the time for every alogrithm.

    Notice, After the first alogrithm the array is already sorted !!! so
    it will work much faster than unsorted array.

    Here are some of my results ( I tried "insertionSort" with
    unsorted and sorted array ) :

    Number of items 50000
    Done with "heap" sort.Time 0[sec]
    Done with "quick" sort.Time 0[sec]
    Done with "merge" sort.Time 0[sec]
    Done with "insertion not sorted" sort.Time 8[sec]
    Done with "insertion already sorted" sort.Time 0[sec]



    Number of items 80000
    Done with "heap" sort.Time 0[sec]
    Done with "quick" sort.Time 0[sec]
    Done with "merge" sort.Time 0[sec]
    Done with "insertion not sorted" sort.Time 22[sec]
    Done with "insertion already sorted" sort.Time 0[sec]




    Here are some of my results ( with out "insertion" sort) :



    Number of items 3500000
    Done with "heap" sort.Time 10[sec]
    Done with "quick" sort.Time 2[sec]
    Done with "merge" sort.Time 3[sec]
    Done with "insertion already sorted" sort.Time 0[sec]


    Which gives you an idea which one is faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Why?!?
    By p3rry in forum C Programming
    Replies: 3
    Last Post: 01-08-2009, 11:52 AM
  2. Help me with function call
    By NeMewSys in forum C++ Programming
    Replies: 16
    Last Post: 05-22-2008, 01:53 PM
  3. Accessing syscalls from C
    By lilcoder in forum C Programming
    Replies: 17
    Last Post: 09-19-2007, 02:27 PM
  4. edit controls in dialogs
    By Homunculus in forum Windows Programming
    Replies: 10
    Last Post: 02-23-2006, 02:38 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21