Monday, April 6, 2009

Sorting .....Comparison Sort

Sorting is a technique which is defined such as,

if A[i] and A[j] are two elements of an array, then the array is sorted if for all i and j

A[i] <= A[j] for all i < style="font-weight: bold;">


You can find the algorithm of QuickSort here on Wikipedia.

I would just touchbase on algo.

QuickSort(int start, int end, int * arr){

if(start < end){
int q = partition(start,end,arr);
This is a recursive defintion of QuickSort. The main function is the partition which returns the index of pivot element. The function runs in a way that if Pivot=arr[end] is the element initially chosen as the pivot. Then at the end of function, the pivot is placed at its correct position q. All the elements with index less than q are smaller than Pivot and all elements greater than q are greater than Pivot. During the entire course of algorithm, Pivot at index q doesn't changes its position.

Iterative version

QuickSort(int start,end, arr){

bounds = {start,end}

bound = popStack()
while(bound.lowerVal < q =" partition(lower,upperval,arr)"> end-1){
Tempbounds = (start,q-1)
bound.lowerVal = q+1
Tempbounds = {q+1,end)
bound.upperVal = q-1
pushStack(Tempbounds )

You can find the C implementation of this code on
Download QuickSort.

1 comment: