Quick, Insertion, and Partition

[silicon]

Hi everyone, I am still having a few issues with my program. It definitely runs but it just seems to run poorly. I think my problem lies within the following 3 sections
Quicksort, Partition, and Insertion

I've written comments next to each line of code just to make sure that I understand it properly. Can you please let me know if I am mistaken in one of the comments or what I am missing. It was easier when the program didn t work. I could look at the error and fix it. Now that it works it seems harder to get it to work properly. I just want to make sure I understand what every line does in Quick, Partition, and Insertion just so I can rewrite any line on my own if needed.

Thanks in advance

//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 = 100000;


ofstream outf("c:\\Output.txt",ios::app);//This prints the results to the c:drive



int main()
{

  
  long random_array[MAX_ARRAY_SIZE];

  long array_sizes[] = {5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000, 60000,65000,70000,75000,80000,85000,90000,95000,100000}; 

  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++)  //Loop goes 20 times.. from 0-19
  {
    num_elements = array_sizes[i];  //First iteration array_sizes[i] which is the 0 location now goes into  num_elements

    getRandomIntegers(random_array, num_elements );  //First iteration...num_elements gets the value of array[i] which is the 0 location WHICH IS 5000. 
													//Random_array gets a number from within the MAX_ARRAY_SIZE  (long random_array[MAX_ARRAY_SIZE];)

    start_time = clock();                           //sTARTS the counter

    QuickSort(random_array, 0, num_elements );      //random which is max array size of 100000 , 5000 number of elements for the firt iteraton

    end_time = clock();								//ends counter

    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;

}

/******************************************************************************/

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

  }



}

/*******************************************************************************/

//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 ) //getRandomIntegers(random_array[max array size of 100000], long array_sizes[] = {5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000, 60000,65000,70000,75000,80000,85000,90000,95000,100000};  

													//Random_array gets a number from within the MAX_ARRAY_SIZE  (long random_array[MAX_ARRAY_SIZE];)

 {
  //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;

}

/******************************************************************************/
[B]//Quick Sort Function[/B]

void QuickSort( long array[], long left, long right)
 {

  if( right <= left )return; // if right (which is the largest number) is less than or equal to left

  long i = Partition( array, left, right );

  QuickSort( array, left, i - 1);  // First subArray left/first to the pivot minus 1

  QuickSort( array, i + 1, right ); //Second subarray pivot+1 to the right/last

}

/******************************************************************************/
[B]//This function partitions the array[/B]


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 element after the pivot (++i) is less than the right

    while( y < array[--r] )  //while right element is less then the element before the right element
		
		if( r == 1 ) //if right location ==1

    break;              //stop

    if( i >= r )        //if left-1 location is greater than or equal to the right location

    break;              //break

    Swap( array[i], array[r] );   //swap  the right element with the left-1 element

  }

   Swap( array[i], array[right] );    //swap the right element with the left-1 element

   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 Insertion( long array[], long left, long right ) [B] //This function seems backwards but when I adjust it it does not run[/B]
 {


  long i;

  for( i = right; i > left; i-- )  //i is equal to the last number.  If i  is greater than the left number (5) then decrease the value of i (7)

    Swap( array[i - 1], array[i] );   //swap the location of array element[i]/right with the location of array element[i-1]

  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;

  }

}

[Dogtree]

Your comments are pretty useless for understanding the algorithm. Sure, you may understand the mechanics of each line taken out of context, but do you understand the purpose of each line when taken as a whole for the algorithm? Comments are better for documenting the reasons for doing something, not for repeating the code in english.

void QuickSort( long array[], long left, long right)
{
  if( right <= left ) return; // Return if there's nothing to partition

  long i = Partition( array, left, right );

  QuickSort( array, left, i - 1);  // Sort the left subarray [left, pivot)
  QuickSort( array, i + 1, right ); // Sort the right subarray [pivot+1, right)
}

long Partition( long array[], long left, long right )
{
  long i = left - 1, r = right;
  long y = array[right]; // Pivot value, (poor choice)

  while( 1 )
  {
    while( array[++i] < y ); // Locate the pivot value index with i
    while( y < array[--r] ) // Locate the pivot value index with r
      if( r == 1 ) break;

    if( i >= r ) break; // Finished if the indexes cross

    Swap( array[i], array[r] ); // Place values less than the pivot at lower
                      // indices and values greater or equal at higher indices
  }

  Swap( array[i], array[right] ); // Place the pivot in its final location

  return i; // Return the pivot index
}