The following are the steps to set up Quick Sort in Data Structures.
- Select first moment of Array A(or sub array) as pivot.
- Initiative and J to first and last elements of the array respectively.
- Increment : until A[i]>pivot;stop
- Decrement : until A[j]<pivot,stop
- if i<j : change A[i] and A[j]
- Repeat statements 3,4 and 5 until i>j, i.e when i and j cross each other.
- Exchange the pivot element with the element pointed to by J which is correct place for pivot
Note that in step 7, The swapping keeps the larger element to the right and smaller element to the left, relative to the pivot.
Quick Sort Program
Implementation of Quick sort
void Quick sort(int k, int lb,int vb);
printf(“How many numbers:”);
printf(“\n Enter the numbers: \n”);
printf(“The following are the sorted elements :\n”);
void quick sort(int k, int lb, int vb)
while(k[i]<key && i<ub)
While(k[j]>key && j>lb)
How many numbers :
Enter the numbers:
The running time of sorting algorithm is usually measured by the number f(n) of comparison required to sort ‘n’ elements, the quick sort algorithm which has many variations as been studied extensively generally speaking, The algorithm has a worst case running time of order n2/2=o(n2) it’s an average cape running time of order o(nlogn)