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;

  }

}

---

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