Quick Sort

The quicksort is considered to be very efficient,  with its "divide and conquer" algorithm.  This sort starts by dividing the original array into two sections (partitions) based upon the value of the first item in the array.  Since our example sorts into descending order, the first section will contain all the elements with values greater than the first item.  The second section will contain elements with values less than (or equal to) the first element. It is possible for the first element to end up in either partition.  Let's examine our same example:

//Quick Sort Functions for Descending Order
// (2 Functions)
void quicksort(apvector <int> &array, int top, int bottom)
{
      // top = subscript of beginning of vector being considered
      // bottom = subscript of end of vector being considered
      // this process uses recursion - the process of calling itself
     int middle;
     if (top < bottom)
    {
          middle = partition(array, top, bottom);
          quicksort(array, top, middle);   // sort top partition
          quicksort(array, middle+1, bottom);    // sort bottom partition
     }
     return;
}

//Function to determine the partitions
// partitions the array and returns the middle index (subscript)
int partition(apvector <int> &array, int top, int bottom)
{
     int x = array[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
           do     
           {
                  j - -;
           }while (x >array[j]);

          do  
         {
                 i++;
          } while (x <array[i]);

          if (i < j)
         { 
                 temp = array[i];    // switch elements at positions i and j
                 array[i] = array[j];
                 array[j] = temp;
         }
     }while (i < j);    
     return j;           // returns middle index
}