QuickSort Algorithm
QuickSort is a sorting algorithm based on the divide and conquer strategy.
- Quick Sort algorithm beings execution by selecting the pivot element, which is usually the last element in the array.
- The pivot element is compared with each element before placing it in its final position in the array.
- The elements on the left ( sub-array 1 ) of the pivot element are smaller than the pivot and the elements to the right ( sub-array 2 ) are bigger than the pivot.
- Quick Sort recursively works on each sub-array till all the pivot elements in each sub-array are placed at their final positions.
Vola !! The result is a sorted array.
Algorithm : QuickSort
1. Pick the last element from the array. This is termed as the pivot.
2. Place pivot it in its final position in the array, such that
the elements to its left are less than itself and the elements to the right of the pivot is greater than itself.
3. Partition the array at the pivot.
Partition A : Begins from the start of array till just before the pivot.
Partition B : Begins from element just after pivot till the end of the array.
4. Recursively apply steps 1, 2 and 3 to each partitioned sub-array A and B.
Example run of the QuickSort algorithm
- At every step we compare the elements from start till end with the pivot element ( last element ).
After the pivot is placed at its final position in the array, the elements to its left should be less than or equal to the pivot and the element to its right should be greater that the pivot. - i keeps track of all the elements that are compared with the pivot.
- j keeps track of all the elements that are less than the pivot and would be placed to the left of the pivot.
Once the pivot is placed in its final position, we get 2 partitions
- Partition 1 [ 3 5 2 4 1 ] to the left of pivot 6.
- Partition 2 [ 8 7 ] to the right of pivot 6.
We continue to apply the QuickSort algorithm recursively on both the partitions.
Example
Time complexity of QuickSort
-
Best / average case : O ( n . log ( n ) ) in most balanced scenarios, when the generated partitions have nearly equal elements. Thus for a balanced case, the depth of the recursion tree is log2 ( n ) and the reordering at each recursion level takes O ( n ) time.
Thus giving the time complexity O ( n . log ( n ) ) -
Worst case : O ( n2 ) when the array is already sorted, the pivot element will require n comparisons to deduce that it remains in its position at the end. Furthermore, the first partition would be empty, but the second partition will have (n-1) elements. Similarly, the pivot in the second partition will need (n-1) comparisons to deduce that it remains in its position at the end and so on. Consequently there will be a total of F(n) = n + (n-1) + (n-2) + .. + 2 + 1 comparisons. Thus giving a worst-case time complexity of O ( n2 ).
Quicksort Implementation
#!/usr/bin/python3
from typing import List # For annotations
def Partition (array : List[int], start : int, end : int):
j = start
# Keep placing elements less than the pivot (array[end]) element to the left
for i in range(start, end):
if (array[i] < array[end]):
# Swap array[i] with array[j]
array[i], array[j] = array[j], array[i]
j += 1
# Place the pivot (array[end]) at its final position and return the pivot index
# for partitioning the array
# Swap array[j] with array[end]
array[j], array[end] = array[end], array[j]
return j
def QuickSort (array : List[int], start : int, end : int):
p = None; # Tracks partition
if (start < end):
p = Partition (array, start, end)
QuickSort (array, start, p-1)
QuickSort (array, p+1, end)
def main():
array = [7, 3, 5, 2, 4, 1, 8, 6]
print("Unsorted array: " + str(array))
QuickSort(array, 0, len(array)-1)
print("Sorted array using Quicksort: " + str(array))
if __name__ == "__main__":
main()
Output
Unsorted array: [7, 3, 5, 2, 4, 1, 8, 6]
Sorted array using Quicksort: [1, 2, 3, 4, 5, 6, 7, 8]
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int Partition(vector<int>& vec, int start, int end) {
int& pivot = vec[end];
int j = start;
// Keep placing elements less than the pivot element
// to the left
for (int i=start; i<end; i++) {
if (vec[i] < pivot) {
swap(vec[i], vec[j]);
j++;
}
}
// Place the pivot at its final position and return the pivot index
// for partitioning the array
swap(vec[j], pivot);
return j;
}
void QuickSort (vector<int>& vec, int start, int end) {
int p;
if (start < end) {
p = Partition (vec, start, end);
QuickSort (vec, start, p-1);
QuickSort (vec, p+1, end);
}
}
int main()
{
vector<int> vec = {7, 3, 5, 2, 4, 1, 8, 6};
QuickSort(vec, 0, vec.size()-1);
cout << "Sorted numbers : ";
for(auto& it: vec)
cout << it << " ";
return 0;
}
Output
Sorted numbers : 1 2 3 4 5 6 7 8
class Sort {
int Partition(int array[], int start, int end) {
int pivot = array[end];
int j = start;
// Keep placing elements less than the pivot element to the left
for (int i=start; i<end; i++) {
if (array[i] < pivot) {
// Swap array[i] with array[j]
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
j++;
}
}
// Place the pivot i.e array[end] at its final position and return the pivot index
// for partitioning the array
int tmp = array[j];
array[j] = array[end];
array[end] = tmp;
return j;
}
void QuickSort (int array[], int start, int end) {
int p;
if (start < end) {
p = Partition (array, start, end);
QuickSort (array, start, p-1);
QuickSort (array, p+1, end);
}
}
public static void main(String args[]) {
int array[] = {7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9};
System.out.print("Unsorted array : ");
for (int i=0; i<array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
Sort s = new Sort();
s.QuickSort(array, 0, array.length-1);
System.out.print("Sorted array using Quick Sort : ");
for (int i=0; i<array.length; i++)
System.out.print(array[i]+" ");
}
}
Output
Unsorted array : 7 3 5 2 4 1 8 6 0 10 9
Sorted array using Quick Sort : 0 1 2 3 4 5 6 7 8 9 10