Quick Sort
- One of the sorting algorithms to arrange elements in sorted order.
- Quick sort is not fastest algorithm.
- Quick sort follows “Divide and conquer” method.
- We recursively partition the input array to arrange the elements in sorted order.
pivot:
- It is location in the input array.
- We select any element in the array is “pivot” mostly first element in the list.
- The concept of quick sort is select of pivot and arranges the elements using pivot location.
Work flow:
We considered first element as pivot element:
- We need to find pivot value position in the array by arranging remaining elements.
- Take 2 variables i and j and assign with values 0 and n
- Move “i” value in forward direction.
- Move “j” value in backward direction.
- Stop “i” if you find the element is greater than or equal to pivot element
- Stop “j” if you find the element is lesser than pivot element
Swap ith location element and jth location element:
Continue the Process until i<j :
After swap:
Next move:
After swap:
Next Move:
After swap, pivot gets its position exactly where it has to be in the array:
Now we need to partition the array according to pivot element and sort them.
Code for partitions:
| int partition(l, h) { pivot = arr[l]; i=l; j=h; while(i<j){ do{ i++; }while(arr[i] <= pivot); do{ j–; }while(arr[j] > pivot); if(i<j) swap(arr[i], arr[j]); } swap(arr[l], arr[j]); return j; } |
- In the above code, partition() function returns j value.
- “j” value is useful as “infinity(higher value)” for left side partition sort.
We sort the element by calling partition function form Quick sort recursive function:
| QuickSort(l, h) { if(l<h) { j = partition(l, h); QuickSort(l, j); QuickSort(j+1, h); } } |