Quicksort

"The quicksort algorithm has a worst-case running time of  Θ(n^2 ) on an input array of n numbers. Despite this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is Θ(nlgn), and the constant factors hidden in the Θ(nlgn) notation are quite small. It also has the advantage of sorting in place, and it works well even in virtual-memory environments."  [Introduction to algorithms]



The following procedure implements quicksort:

Quicksort( int a[],  int p, int r)
if p < r
   q = Partition(a, p, r) // q is the position of the partition s.t. the element
                      // before a[q] is smaller than a[q], and greater after that.
   Quicksort(a, p, q-1)
   Quicksort(a, q+1, r)




The following procedures are two ways to implement partition:

First way (from Introduction to Algorithms):
Partition(int a[],  int p, int r)

x = a[r]  // x is the pivot: always selects a[r] as the pivot
i = p - 1  // i+1 indicates the position of the partition(pivot) 
//in the resulting array
// the following loop moves elements smaller than the pivot into 
//the front of the array
// i indicates the highest position of it
for j = p to r - 1
     if a[j] <= x  //if a[j] is larger than the pivot, do nothing, otherwise...
          i = i  + 1
          exchange a[i] with a[j]
exchange a[i+1] with a[r]   // finally, move the pivot to the position s.t.  
//the element

                             // before a[i+1] is smaller than a[i+1],
// and greater after that.

return i + 1



Second way:
partition(int array[], int low, int high)

//low= the index of the first element; high= the index of the last element
int partition(int array[], int low, int high)
{
    // The pivot is choosen to be the first element
    int pivot = array[low];

    // After the while loop, the position of the pivot is moved to somewhere 
    // in the middle and the elements to leftside of the pivot are smaller than it
    // and meanwhile, the elements to its right are larger than it.
    while (low < high)
    {
        // The fowlloing two  while loops will move low and high index
        // so that the elements to left of low are smaller than the pivot
        // and the elements to the right of high are larger than the pivot
        //  begining: (low)---------------high
        //  after the while loops:  -- pivot ---
        while (low < high && array[high] >= pivot)
        {
            --high;
        }

        swap(array[low], array[high]);

        while (low < high && array[low] <= pivot)
        {
            ++low;
        }


        swap(array[low], array[high]);
     }

    return low;
}