Insertion Sort Problem

silicon · #1 08-May-2005, 00:02

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++...it will however work on Borland c++

CPP / C++ / 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;

  }

}

silicon · #2 08-May-2005, 12:29

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

Sokar · #3 08-May-2005, 16:13

First I would say lets shrink down the code to a smaller working program with just the part you are interested in. I also added some code to print the array in the function.

CPP / C++ / C Code:

#include <iostream>
#include <conio.h>
#include <ctime>
#include <limits>
#include <cstdlib>
#include <fstream>
#include <cmath>
using namespace std; 

//Function-will swap two long integer numbers
void Swap (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;

int main()
{
	//This function will use a for loop to call the different sort functions,
	//with varing array sizes.
	const long MAX_ARRAY_SIZE = 11;
	long random_array[MAX_ARRAY_SIZE]={7, 2, 9, 5, 3, 1, 10, 11, 15, 21, 0};
 
	//long array_sizes[] = {100000, 110000, 130000, 150000, 170000, 190000, 200000, 210000, 230000, 250000, 255000, 260000};
	long num_elements;

	num_elements = 11;

	Insertion( random_array, 0, num_elements );

	getch();
	return 0;
}

/**************************************************  ****************************/
//Swap function, accepts two long integer values and swaps them.

void Swap( long &first, long &second )
{
	long temp;

	temp = first;
	first = second;
	second = temp;
}

/**************************************************  ****************************/
void Insertion( long array[], long left, long right )
{
	long i;

//print array
	for(int q = 0; q < 11; q++ )
		cout << array[q] << endl;
	cout << endl;
//end print

	for( i = right; i > left; i-- )
		Swap( array[i - 1], array[i] );

//print array
	for(int q = 0; q < 11; q++ )
		cout << array[q] << endl;
	cout << endl;
//end print

	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;
	}
//print array
	for(int q = 0; q < 11; q++ )
		cout << array[q] << endl;
	cout << endl;
//end print
}

Quote:

Originally Posted by silicon

unfortunately he didnt give me the greatest explanation as to why this actually works.

Are you sure it works?
I have added the values that you have in you example.
7 2 9 5 3 1 10 11 15 21 which is ten elements and I added one and gave it the value 0 to make it 11.
In main the values that is passed as "right" is num_elements that has the value 11.
So lets take a little closer look and replace some variables with the corresponding values.
So this

CPP / C++ / C Code:

for( i = right; i > left; i-- )
	Swap( array[i - 1], array[i] );

would look like this,

CPP / C++ / C Code:

for( i = 11; i > 0; i-- )
	Swap( array[11 - 1], array[11] );

but the index of the array with 11 elements is 0 to 10 not 0 to 11. So that is accessing an out of bounds spot.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Merge sort on a linked list	Temujin_12	C++ Forum	1	06-Mar-2008 20:33
Graphic problem in Unreal Tournament 2004	zerox	Computer Software Forum - Games	10	09-Oct-2005 12:31
Sorting Algorithms by Time	silicon	C++ Forum	4	02-May-2005 21:54
bucket sort problem	ap6118	C++ Forum	3	15-Apr-2005 18:02
Another FX 5600 problem (but with details that might shed light on this)	BobDaDuck	Computer Hardware Forum	2	16-Apr-2004 07:53

Insertion Sort Problem

Insertion Sort-Code Does not make sense