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.

sorting data in Pivot report

ReplyDelete