Thread: Insertion Sort Problem

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    Insertion Sort Problem

    Hello everyone, I just wanted to thank you in advance for all of your help.
    My code is now working properly except for one thing. The insertion part feels like it takes about 5 minutes to complete. I know that this method is the slowest of the 4
    I was wondering if there a problem with the way it was written
    My partner wrote this insertion sort function and it does work...but runs very slowly and I am having problems adjusting
    it since this code will not work on Visual C++ (gives me an exe error) ...it will however work on Borland c++

    Code:
      
    
    #include <iostream.h>
    #include <conio.h>
    #include <time.h>
    #include <limits.h>
    #include <stdlib.h>
    #include <fstream.h>
    #include <math.h>
    
    //Function-fills the array with random integers
    void getRandomIntegers (long [], long);
    
    //Function-will swap two long integer numbers
    void Swap (long &, long &);
    
    //Function-works with HeapSort to rearrange and adjust the heap
    void Heapify (long [], long, long);
    
    //Function-will be used with QuickSort to partition array
    long Partition (long [], long, long);
    
    //Function-sorts the array using the QuickSort method
    void QuickSort (long [], long, long);
    
    //Function-sorts the array using the MergeSort method
    void MergeSort (long [], long, long);
    
    //Function will be used with MergeSort to merge array back together.
    void Merge (long [], long, long, long);
    
    //Function-sorts the array using the HeapSort method
    void HeapSort (long [], long, long);
    
    //Function-sorts the array using the Insertion method
    void Insertion (long [], long, long);
    
    
    //Global variable constant
    //This will be used by the various sorting functions
    long const MAX_ARRAY_SIZE = 260000;
    
    
    ofstream outf("c:\\Output.txt",ios::app);//This prints the results to the c:drive
    
    
    int main()
    {
    
    //This function will use a for loop to call the different sort functions,
    //with varing array sizes.
    
       
    
    
      long random_array[MAX_ARRAY_SIZE];
    
      long array_sizes[] = {100000, 110000, 130000, 150000, 170000, 190000, 200000, 210000, 230000, 250000, 255000, 260000}; 
    
      long num_elements;
    
      clock_t start_time, end_time;
    
      srand( time( NULL ));// This generates the random numbers
    
      cout << "Sort Type\t\t# of Elements\t\t\tTime(s)\n";
    
      cout << "--------\t\t-------------------\t\t-------\n";
    
      outf << "Sort Type\t\t# of Elements\t\t\tTime(s)\n";
    
      outf << "--------\t\t-------------------\t\t-------\n";
    
      for(long i = 0; i < 20; i++)
      {
        num_elements = array_sizes[i];
    
        getRandomIntegers(random_array, num_elements );
    
        start_time = clock();
    
        QuickSort(random_array, 0, num_elements );
    
        end_time = clock();
    
        cout << "Quick   \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
    
        outf<< "Quick    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
    
        getRandomIntegers( random_array, num_elements );
    
        start_time = clock();
    
        MergeSort( random_array, 0, num_elements );
    
        end_time = clock();
    
        cout << "Merge    \t\t\t" << num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
    
        outf << "Merge    \t\t\t" << num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
    
        getRandomIntegers( random_array, num_elements );
    
        start_time = clock();
    
        HeapSort( random_array, 0, num_elements );
    
        end_time = clock();
    
        cout << "Heap    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
    
        outf << "Heap    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
    
        getRandomIntegers( random_array, num_elements );
    
        start_time = clock();
    
        Insertion( random_array, 0, num_elements );
    
        end_time = clock();
    
        cout << "Insertion    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC<< endl << endl;
    
        outf << "Insertion    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl<<endl;
    
      }
      getch();
      return 0;
    
    }
    
    /******************************************************************************/
    
    //This function is used by HeapSort to adjust the heap or "rearrange a heap to maintain the heap property"
    void Heapify( long array[], long item, long num )
     {
    
      while( 2 * item <= num )
      {
        long j = 2 * item;
    
        if( j < num && array[j] < array[j + 1] ) j++;
    
        if( !( array[item], array[j]))
    
        break;
    
        Swap( array[item], array[j] ); item = j;
    
      }
    
    }
    
    /******************************************************************************/
    
    void getRandomIntegers ( long arr[], long b )
     {
      //Fills an array(the first paramater) with
    
      //a specified amount( the second parameter ) of random integers.
    
      //The range of the random numbers will be from 0 to RAND_MAX.
    
    
    
      for( long i = 0; i < b; i++ )
    
        arr[i] = rand();
    
    }
    
    /******************************************************************************/
    //Swap function, accepts two long integer values and swaps them.
    
    void Swap( long &first, long &second )
     {
    
      long temp;
    
      temp = first;
    
      first = second;
    
      second = temp;
    
    }
    
    /******************************************************************************/
    //Quick Sort Function
    
    void QuickSort( long array[], long left, long right)
     {
    
      if( right <= left )return;
    
      long i = Partition( array, left, right );
    
      QuickSort( array, left, i - 1);
    
      QuickSort( array, i + 1, right );
    
    }
    
    /******************************************************************************/
    //This function partitions the array
    
    
    long Partition( long array[], long left, long right )
    {
    
    
      long i = left - 1, r = right;
    
      long y = array[right];
    
      while( 1 )
      {
        while( array[++i] < y );
    
        while( y < array[--r] )if( r == 1 )
    
        break;
    
        if( i >= r )
    
        break;
    
        Swap( array[i], array[r] );
    
      }
    
       Swap( array[i], array[right] );
    
       return i;
    
    }
    
    /******************************************************************************/
    //MergeSort function
    
    void MergeSort( long array[], long left, long right )
    {
    
    
      if( right <= left )
    
      return;
    
      long middle = ( right + left )/2;
    
      MergeSort( array, left, middle );
    
      MergeSort( array, middle + 1, right );
    
      Merge( array, left, middle, right );
    
    }
    
    /******************************************************************************/
    //Merges arrays back together after they are split
    
    void Merge( long array[], long left, long middle, long right )
    {
    
    
      long i, j;
    
      long  static temp[MAX_ARRAY_SIZE];
    
      for( i = middle + 1; i > left; i-- )
    
        temp[i - 1] = array[i - 1];
    
      for( j = middle; j < right; j++ )
    
        temp[right + middle - j] = array[j + 1];
    
      for( long k = left; k <= right; k++ )
    
        if( temp[j] < temp[i] )
    
          array[k] = temp[j--];
    
        else
    
          array[k] = temp[i++];
    
    }
    
    /******************************************************************************/
    
    
    void HeapSort( long array[], long left, long right )
    {
    
      long k, num = right - left + 1;
    
      long *ip = array + left - 1;
    
      for( k = num/2; k >= 1; k-- )
    
      Heapify( ip, k, num );
    
      while ( num > 1 )
      {
    
        Swap( ip[1], ip[num] );
    
        Heapify( ip, 1, --num );
    
      }
    
    
    
    }
    
    /******************************************************************************/
    
    void Insertion( long array[], long left, long right )
     {
    
    
      long i;
    
      for( i = right; i > left; i-- )
    
        Swap( array[i - 1], array[i] );
    
      for( i = left + 2; i <= right; i++ )
       {
    
        long j = i, item = array[i];
    
        while( item < array[j - 1] )
    
        {
    
        array[j] = array[j - 1];
        j--;
    
        }
    
        array[j] = item;
    
      }
    
    }

  2. #2
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    Insertion Sort Problem-Code does not make sense

    Hi, someone has explained the previous question to me but I still cannot figure out this section of my partners code. I am trying to draw out a picture of this but it does not make any sense.

    Lets say for instance the array is
    7 2 9 5 3 1 10 11 15 21

    I understand that insertion sort basically you would extract the element and the remaining elements would shift to accommodate the insertion of the element that was extracted into its correct location. This would happen recursively until completed
    I am sure that there is a simpler way of writing this and unfortunately he didnt give me the greatest explanation as to why this actually works. This code looks completely backwards to me

    Code:
    void Insertion( long array[], long left, long right )
     {
    
    
      long i; 
    
      for( i = right; i > left; i-- ) //I is equal to right....If i is greater than left then do the swap we have which will swap the two elements below
    
        Swap( array[i - 1], array[i] );  swap element [i-1] with array [i]
    so array[i]'s element is now array[i-1]
    
      for( i = left + 2; i <= right; i++ ) //this is the part that doesnt make any sense.
       {
    
        long j = i, item = array[i];
    
        while( item < array[j - 1] )
    
        {
    
        array[j] = array[j - 1];
        j--;
    
        }
    
        array[j] = item;
    
      }
    
    }
    I wanted to rewrite this entire section so that I could make some sense of it and explain it to my group. PLease let me know if you also know of a tutorial that would help me with this

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem with gets and bubble sort
    By wwwildbill in forum C Programming
    Replies: 4
    Last Post: 04-04-2009, 01:31 AM
  2. Shell Sort with Vectors Problem
    By TheSpoiledMilk in forum C++ Programming
    Replies: 4
    Last Post: 11-22-2005, 03:05 PM
  3. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  4. netonotisr inor (insertion sort)
    By The Brain in forum C++ Programming
    Replies: 0
    Last Post: 05-04-2005, 03:11 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM