QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
Quicksort works like this.
An example of quicksort.
Consider the following array: 50, 23, 9, 18, 61, 32
. We need to sort this array in the most efficient manner without using extra place (inplace sorting).
Step 1:
23, 50, 9, 18, 61, 32
23, 9, 50, 18, 61, 32
.23, 9, 18, 50, 61, 32
. Now 61 is greater than pivot (32), hence no changes.Thus the pivot (32) comes at its actual position and all elements to its left are lesser, and all elements to the right are greater than itself.
Step 2: The main array after the first step becomes
23, 9, 18, 32, 61, 50
Step 3: Now the list is divided into two parts:
Step 4: Repeat the steps for the left and right sublists recursively. The final array thus becomes
9, 18, 23, 32, 50, 61
.
public int[] sort(int[] array, int low, int high) { if (low < high) { // find pivot element such that // elements smaller than pivot are on the left // elements greater than pivot are on the right int pi = partition(array, low, high); // recursive call on the left of pivot sort(array, low, pi - 1); // recursive call on the right of pivot sort(array, pi + 1, high); } return array; } // method to find the partition position int partition(int array[], int low, int high) { // choose the rightmost element as pivot int pivot = array[high]; // pointer for greater element int i = (low - 1); // traverse through all elements // compare each element with pivot for (int j = low; j < high; j++) { if (array[j] <= pivot) { // if element smaller than pivot is found // swap it with the greatr element pointed by i i++; // swapping element at i with element at j int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // swapt the pivot element with the greater element specified by i int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; // return the position from where partition is done return (i + 1); }
Is Quick Sort a stable algorithm?
Quick sort is not a stable algorithm because the swapping of elements is done according to pivot’s position (without considering their original positions). A sorting algorithm is said to be stable if it maintains the relative order of records in the case of equality of keys.
What is Randomised Quick Sort? Why is it used?
O(n log n)
as the selected random pivots are supposed to avoid the worst case behavior.Why Quick Sort is better than Merge Sort?
Which is faster quick sort or merge sort?
Quick sort is faster than the merge sort. Please refer the above question.
Where is quick sort used?
Quick sort is basically used to sort any list in fast and efficient manner. Since the algorithm is inplace, quick sort is used when we have restrictions in space availability too. Please refer to the Application section for further details.