Thread: Simple Sorts Confuse ME =/

  1. #1
    Student otchster's Avatar
    Join Date
    Oct 2005
    Posts
    30

    Simple Sorts Confuse ME =/

    In my class we are learning about different sorting methods. Im kind of confused about all of it, and the fact that functions still confuse me dosen't exaclty help either.

    We have the code provided for:

    Bubble Sort
    Insertion Sort
    Selection Sort
    and Shell Sort

    For this assignment we have to use the four different sorts and calculate system time for how long it takes to sort the data.

    This is said to be easy because I have access to all the code. My prof said it was just simple plugging in of code, but I somehow find a way to get confused and frustrated.

    The assignment calls to edit this code:
    Code:
    #include <stdio.h>
    #include <sys/time.h>   /* includes for gettimeofday() function */
    #include <time.h>       /* includes for system time functions   */
    #define SIZE 100000
    
    struct timeval start, end;   /* declaration for gettimeofday structure */
    time_t starttime, endtime, startmicro, endmicro;
    
    void bubbleSort(int numbers[], int array_size);
    
     int main()
     {
       int i, arrayOfNum[SIZE];
       /* fill array */
       for(i=0; i<SIZE; i++)
       {
         arrayOfNum[i] = SIZE - i;
       }
    
       /* get system time before the sort*/
       gettimeofday(&start,NULL);
       starttime=start.tv_sec;
       startmicro=start.tv_usec;
    
       /* sort array */
       bubbleSort(arrayOfNum, SIZE);
    
       /* get system time after the sort */
       gettimeofday(&end,NULL);
       endtime=end.tv_sec;
       endmicro=end.tv_usec;
       
    
       /* print the elapsed time of the sort */
       printf("The total time elapsed is: %f seconds\n",((endtime-starttime)+((endmicro-startmicro)/1000000.0)));
    
       return 0;
     }
    
     void bubbleSort(int numbers[], int array_size)
     {
       int i, j, temp, count;
    
       count=0;
       for (i = (array_size - 1); i >= 0; i--)
       {
         for (j = 1; j <= i; j++)
         {
           count = count+1;
           if (numbers[j-1] > numbers[j])
           {
             temp = numbers[j-1];
             numbers[j-1] = numbers[j];
             numbers[j] = temp;
           }
         }
       }
       printf("Count = %d\n", count);
     }
    and replace with the other 3 types of sorts.

    here are the remaining sort codes:

    Insertion Sort:
    Code:
    void insertionSort(int numbers[], int array_size)
     {
       int i, j, B, count;
       count = 0;
       for (i = 1; i < array_size; i++)
       {
         j = i;
         B = numbers[i];
         while ((j > 0) && (numbers[j-1] > B))
         {
            count = count + 1;
            numbers[j] = numbers[j-1];
            j--;
         }
         numbers[j] = B;
       }
       printf("Count = %d\n", count);
     }

    Selection Sort:
    Code:
     void selectionSort(int numbers[], int array_size)
     {
       int i, j, T, min, count;
       count = 0;
       for (i = 0; i < array_size; i++)
       {
         min = i;
         for (j = i + 1; j < array_size; j++)
         {
           count = count + 1;
           if (numbers[j] < numbers[min])
           {
              min = j;
           }
         }
         T = numbers[min];
         numbers[min] = numbers[i];
         numbers[i] = T;
       }
       printf("Count = %d\n", count);
     }

    Shell Sort:
    Code:
     void shellSort(int numbers[], int array_size)
     {
       int i, j, h, B, count;
       h = 1;
       count = 0;
       while ((h * 3 + 1) < array_size)
       {
         h = 3 * h + 1;
       }
    
       while( h > 0 )
       {
         for (i = h - 1; i < array_size; i++)
         {
           B = numbers[i];
           j = i;
    
           for( j = i; (j >= h) && (numbers[j-h] > B); j -= h)
           {
             count = count + 1;
             numbers[j] = numbers[j-h];
           }
           numbers[j] = B;
         }
         h = h / 3;
       }
       printf("Count = %d\n", count);
     }


    the original code above printfs everything needed, the only assignment is to plug in the three different sorts, and make an excel chart with the different results.

    ive tried to plug in the new sorts unsuccessfully only to find the system times to all be equal or for the code to not compile correctly..


    thanks for all who help
    Last edited by otchster; 12-03-2005 at 12:24 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So you have 4 sorts

    Code:
    for ( i = 0 ; i < 4 ; i++ ) {
      // init array and start timer
      if ( i == 0 ) bubbleSort(arrayOfNum, SIZE);
      if ( i == 1 ) shellSort(arrayOfNum, SIZE);
      // stop timer and print
    }

  3. #3
    Student otchster's Avatar
    Join Date
    Oct 2005
    Posts
    30
    Quote Originally Posted by Salem
    So you have 4 sorts

    Code:
    for ( i = 0 ; i < 4 ; i++ ) {
      // init array and start timer
      if ( i == 0 ) bubbleSort(arrayOfNum, SIZE);
      if ( i == 1 ) shellSort(arrayOfNum, SIZE);
      // stop timer and print
    }
    im not sure how to understand this. the assignment called to incorporate the different sorts and record the times it took to sort the data.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Yes, and that suggestion means you run all 4 of them, one after another.

    Just take the code you have, and then decide which of 4 sorts to run
    Just 2 more if() statements from where I'm sitting.

  5. #5
    Student otchster's Avatar
    Join Date
    Oct 2005
    Posts
    30
    could i see an example code. the excerpt is confusing me. thx

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Oh for heavens sake
    Code:
     int main()
     {
       int t, i, arrayOfNum[SIZE];
      for ( t = 0 ; t < 4 ; t++ ) {
       /* fill array */
       for(i=0; i<SIZE; i++)
       {
         arrayOfNum[i] = SIZE - i;
       }
    
       /* get system time before the sort*/
       gettimeofday(&start,NULL);
       starttime=start.tv_sec;
       startmicro=start.tv_usec;
    
       /* sort array */
       if ( t == 0 ) bubbleSort(arrayOfNum, SIZE);
       if ( t == 1 ) insertSort(arrayOfNum, SIZE);
       if ( t == 2 ) shellSort(arrayOfNum, SIZE);
       if ( t == 3 ) selectionSort(arrayOfNum, SIZE);
    
       /* get system time after the sort */
       gettimeofday(&end,NULL);
       endtime=end.tv_sec;
       endmicro=end.tv_usec;
       
    
       /* print the elapsed time of the sort */
       printf("The total time elapsed is: %f seconds\n",((endtime-starttime)+((endmicro-startmicro)/1000000.0)));
      }
       return 0;
     }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. creating very simple text editor using c
    By if13121 in forum C Programming
    Replies: 9
    Last Post: 10-19-2010, 05:26 PM
  2. Simple message encryption
    By Vicious in forum C++ Programming
    Replies: 10
    Last Post: 11-07-2004, 11:48 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Simple simple program
    By Ryback in forum C++ Programming
    Replies: 10
    Last Post: 09-09-2004, 05:48 AM
  5. Need help with simple DAQ program
    By canada-paul in forum C++ Programming
    Replies: 12
    Last Post: 03-15-2002, 08:52 AM