Quick Sort

This article explores an algorithm which sorts an array recursively using a very popular algorithm called quick sort. The name comes from the fact that, in general, quick sort can sort a list of data elements significantly faster than any of the common sorting algorithms. This algorithm is based on the fact that it is faster and easier to sort two small arrays than one larger one. The basic strategy of quick sort is to divide and conquer.

If you were given a large stack of papers bearing the names of the students to sort them by name, you might use the following approach: Pick a splitting value, say L, and divide the stack of papers into two piles, A-l and M-Z. (Note that the two piles will not necessarily contain the same number of papers.) Then take the first pile and subdivide it into two piles, A-F and G-L. The A-F pile can be further broken down into A-C and D-F. This division process goes on until the piles are small enough to be easily sorted. The same process is applied to the M-Z pile. Eventually all the small sorted piles can be stacked one on top of the other to produce an ordered set of papers.

This strategy is based on recursion - on each attempt to sort the stack of papers the pile is divided and then the same approach is used to sort each smaller piles (a smaller case). The arguments being passed to the function quick( ) would reflect the part of the array that is being currently processed :We will pass the first and last indices that define the part of the array to be processed on this call. The initial call to quick( ) would contain the parameters 0 and 9, since there are 10 integers in our array.

And now the program which implements this concept.

int arr[10] = { 7, 3, 1, 19, 13, 15, 5, 17, 9, 11 } ;

main( )

{

int i ;

printf ( "\nArray before sorting:\n" ) ;

for ( i = 0 ; i < 10 ; i++ )

printf ( "%d ", arr[i] ) ;

quick ( 0, 9 ) ;

printf ( "\nArray after calling Quick Sort is:\n" ) ;

for ( i = 0 ; i < 10 ; i++ )

printf ( "%d ", arr[i] ) ;

}

quick ( int low, int high )

{

int pos ;

if ( low < high )

{

split ( low, high, &pos ) ;

quick ( low, pos - 1 ) ;

quick ( pos + 1, high ) ;

}

}

/* split() chooses the splitting value and rearranges the array so that all elements to the left of split value are less than or equal to it and all elements greater that the split value are to the right of it. */

split ( int low, int high, int *p )

{

int item, i, j, t ;

item = arr[low] ;

i = low ;

j = high ;

while ( i < j )

{

/* move from R to L in search of element < item */

while ( arr[j] > item )

j = j - 1 ;

/* move from L to R in search of element > item */

while ( arr[i] <= item && i < j )

i = i + 1 ;

if ( i < j )

{

t = arr[i] ;

arr[i] = arr[j] ;

arr[j] = t ;

}

}

*p = j ;

t = arr[low] ;

arr[low] = arr[*p] ;

arr[*p] = t ;

}

How can we compare the efficiency of this sorting algorithm with others? We pick up an operation central to the sorting algorithm - the number of comparisons made. We can then relate the number of comparisons made to the number of elements in the array as a rough measure of the efficiency of each algorithm. This measure is often known as the order of magnitude. The order of magnitude of common sorting algorithms like bubble sort, selection sort, exchange sort is O(n2). Can you guess why quick sort's order of magnitude is O(log2n)?