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++

#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;

  }

}

>I was wondering if there a problem with the way it was written
Aside from being copied verbatim from a book that is well known for its awful code (poorly written in C via Pascal), there's nothing wrong with the code except for the first loop should do a conditional swap, not an unconditional swap.

>but runs very slowly
Wow, what a shocker. You're performing multiple quadratic sorts on arrays that have over 100000 randomly permuted items. No amount of tweaking with fix that.

>since this code will not work on Visual C++
Your array size is probably overflowing the stack. 260000 is somewhat large for a static array on some implementations. Using dynamic allocation will probably fix it:

long *random_array = new long[MAX_ARRAY_SIZE];

Hello use the following insertion sort routine a template based version.

//This routine does the insertion sort
//This sorts array of object of template class T (T arr[]) & no. of elements in the array (int n)
template <class T>
void insertionSort(T arr[], int n)
{
	for (int i = 1; i < n; i++)
	{
		//start from 2nd node onwards
		T val = arr[i];

		for (int j = i - 1; j >= 0; j--)
		{
			if (arr[j] > val)
			{
				arr[j+1] = arr[j];
			}
			else
				break;
		}
		arr[j+1] = val;
	}

}

Code tags added. -Narue

* Above is compiled and running on VC6.0 & i dont think will give hitch for porting on unix/linux/.NET.
*Doesn't have runtime issues..use it & give feedback
--------------------------------------------------------------------------


>I was wondering if there a problem with the way it was written
Aside from being copied verbatim from a book that is well known for its awful code (poorly written in C via Pascal), there's nothing wrong with the code except for the first loop should do a conditional swap, not an unconditional swap.

>but runs very slowly
Wow, what a shocker. You're performing multiple quadratic sorts on arrays that have over 100000 randomly permuted items. No amount of tweaking with fix that.

>since this code will not work on Visual C++
Your array size is probably overflowing the stack. 260000 is somewhat large for a static array on some implementations. Using dynamic allocation will probably fix it:

long *random_array = new long[MAX_ARRAY_SIZE];

>Hello use the following insertion sort routine a template based version.
I don't see how your solution would have any effect on the OP's problem.

>i dont think will give hitch for porting on unix/linux/.NET
It fails to compile on any conforming compiler.

>Doesn't have runtime issues
The algorithm may not have run-time issues when you tested it, but the sort function is not what the problem was.

This article has been dead for over six months. Start a new discussion instead.