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

QuickSort.

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);
QuickSort(start,q-1,arr)
QuickSort(q+1,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}
pushToStak(bounds);

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

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

1 comment: