How does QuickSort Algorithm work?
There are mainly three steps in the algorithm.
1. Choose a pivot
2. Partition the array around pivot. After partition, it is ensured that all elements are smaller than all right and we get index of the end point of smaller elements. The left and right may not be sorted individually.
3. Recursively call for the two partitioned left and right subarrays.
4. We stop recursion when there is only one element is left.
Choice of Pivot:
There are many different choices for picking pivots.
- Always pick the first (or last) element as a pivot. The below implementation is picks the last element as pivot. The problem with this approach is it ends up in the worst case when array is already sorted.
- Pick a random element as a pivot. This is a preferred approach because it does not have a pattern for which the worst case happens.
- Pick the median element is pivot. This is an ideal approach in terms of time complexity as we can find median in linear time and the partition function will always divide the input array into two halves. But it is low on average as median finding has high constants.
Partition Algorithm:
The key process in quickSort is a partition(). There are three common algorithms to partition. All these algorithms have O(n) time complexity.
1. Naive Partition : Here we create copy of the array. First put all smaller elements and then all greater. Finally we copy the temporary array back to original array. This requires O(n) extra space.
2. Lomuto Partition : We have used this partition in this article. This is a simple algorithm, we keep track of index of smaller elements and keep swapping. We have used it here in this article because of its simplicity.
3. Hoare’s Partition : This is the fastest of all. Here we traverse array from both sides and keep swapping greater element on left with smaller on right while the array is not partitioned. Please refer Hoare’s vs Lomuto for details.
Below diagram illustrates overview of the algorithm using last element as pivot and Lomuto partition,
How Quicksort works
Details of the Partition Algorithm and Illustration :
The logic is simple, we start from the leftmost element and keep track of the index of smaller (or equal) elements as i . While traversing, if we find a smaller element, we swap the current element with arr[i]. Otherwise, we ignore the current element.
Let us understand the working of partition and the Quick Sort algorithm with the help of the following example:
Consider: arr[] = {10, 80, 30, 90, 40}.
- Compare 10 with the pivot and as it is less than pivot arrange it accordingly.
Partition in QuickSort: Compare pivot with 10
- Compare 80 with the pivot. It is greater than pivot.
Partition in QuickSort: Compare pivot with 80
- Compare 30 with pivot. It is less than pivot so arrange it accordingly.
Partition in QuickSort: Compare pivot with 30
- Compare 90 with the pivot. It is greater than the pivot.
Partition in QuickSort: Compare pivot with 90
- Arrange the pivot in its correct position.
Partition in QuickSort: Place pivot in its correct position
Illustration of QuickSort Algorithm:
The partition keeps on putting the pivot in its actual position in the sorted array. Repeatedly putting pivots in their actual position makes the array sorted.
Follow the below images to understand how the recursive implementation of the partition algorithm helps to sort the array.
- Initial partition on the main array:
Quicksort: Performing the partition
- Partitioning of the subarrays:
Quicksort: Performing the partition
Quick Sort is a crucial algorithm in the industry, but there are other sorting algorithms that may be more optimal in different cases. To gain a deeper understanding of sorting and other essential algorithms, check out our course Tech Interview 101 – From DSA to System Design . This course covers almost every standard algorithm and more.
Code implementation of the Quick Sort:
C++
#include
using namespace std;
int partition(vector<int>& arr, int low, int high) {
// Choose the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = low - 1;
// Traverse arr[;ow..high] and move all smaller
// elements on left side. Elements from low to
// i are smaller after every iteration
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
// Move pivot after smaller elements and
// return its position
swap(arr[i + 1], arr[high]);
return i + 1;
}
// The QuickSort function implementation
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
// pi is the partition return index of pivot
int pi = partition(arr, low, high);
// Recursion calls for smaller elements
// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Sorted Array\n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
C
#include
#include
// Function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
// Choose the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = low - 1;
// Traverse arr[low..high] and move all smaller
// elements on the left side. Elements from low to
// i are smaller after every iteration
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
// Move pivot after smaller elements and
// return its position
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
// The QuickSort function implementation
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is the partition return index of pivot
int pi = partition(arr, low, high);
// Recursion calls for smaller elements
// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted Array\n");
printArray(arr, n);
return 0;
}
Java
// Java implementation of QuickSort
import java.io.*;
class GFG {
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,
// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// To print sorted array
public static void printArr(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.length;
// Function call
quickSort(arr, 0, N - 1);
System.out.println("Sorted array:");
printArr(arr);
}
}
// This code is contributed by Ayush Choudhary
// Improved by Ajay Virmoti
Python
def partition(arr, low, high):
# Choose the pivot
pivot = arr[high]
i = low - 1
# Traverse arr[low..high] and move all smaller
# elements on the left side. Elements from low to
# i are smaller after every iteration
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# Move pivot after smaller elements and
# return its position
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# The QuickSort function implementation
def quick_sort(arr, low, high):
if low < high:
# pi is the partition return index of pivot
pi = partition(arr, low, high)
# Recursion calls for smaller elements
# and greater or equals elements
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
# Function to print an array
def print_array(arr):
for i in arr:
print(i, end=" ")
print()
# Driver code
if __name__ == "__main__":
arr = [10, 7, 8, 9, 1, 5]
print("Given array is")
print_array(arr)
quick_sort(arr, 0, len(arr) - 1)
print("\nSorted array is")
print_array(arr)
C#
// C# implementation of QuickSort
using System;
class GFG {
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,
// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// and after partition index
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Driver Code
public static void Main()
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.Length;
// Function call
quickSort(arr, 0, N - 1);
Console.WriteLine("Sorted array:");
for (int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by gfgking
JavaScript
function partition(arr, low, high) {
// Choose the pivot
const pivot = arr[high];
let i = low - 1;
// Traverse arr[low..high] and move all smaller
// elements on the left side. Elements from low to
// i are smaller after every iteration
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
// Move pivot after smaller elements and
// return its position
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
// The QuickSort function implementation
function quickSort(arr, low, high) {
if (low < high) {
// pi is the partition return index of pivot
const pi = partition(arr, low, high);
// Recursion calls for smaller elements
// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
function printArray(arr) {
console.log(arr.join(" "));
}
// Driver code
const arr = [10, 7, 8, 9, 1, 5];
console.log("Given array is");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
console.log("\nSorted array is");
printArray(arr);
PHP
// code
?>
// This Function takes place last element as pivot
// Place the pivot as correct position
// In Sorted Array, and places all smaller to left
// of pivot and all greater element to its right of pivot
function partition(&$arr,$low,$high)
{
// Choose the Pivot Element
$pivot= $arr[$high];
// Index of smaller element and indicates
// The right position of pivot
$i=($low-1);
for($j=$low;$j<=$high-1;$j++)
{
if($arr[$j]<$pivot)
{
// Increment index of smaller element
$i++;
list($arr[$i],$arr[$j])=array($arr[$j],$arr[$i]);
}
}
// Pivot element as correct position
list($arr[$i+1],$arr[$high])=array($arr[$high],$arr[$i+1]);
return ($i+1);
}
// The main function that implement as QuickSort
// arr[]:- Array to be sorted
// low:- Starting Index
//high:- Ending Index
function quickSort(&$arr,$low,$high)
{
if($low<$high)
{
// pi is partition
$pi= partition($arr,$low,$high);
// Sort the array
// Before the partition of Element
quickSort($arr,$low,$pi-1);
// After the partition Element
quickSort($arr,$pi+1,$high);
}
}
// Driver Code
$arr= array(10,7,8,9,1,5);
$N=count($arr);
// Function Call
quickSort($arr,0,$N-1);
echo "Sorted Array:\n";
for($i=0;$i<$N;$i++)
{
echo $arr[$i]. " ";
}
//This code is contributed by Diwakar Jha
Output
Sorted Array 1 5 7 8 9 10
Time Complexity:
- Best Case : Ω (N log (N))
The best-case scenario for quicksort occur when the pivot chosen at the each step divides the array into roughly equal halves.
In this case, the algorithm will make balanced partitions, leading to efficient Sorting. - Average Case: θ ( N log (N))
Quicksort’s average-case performance is usually very good in practice, making it one of the fastest sorting Algorithm. - Worst Case: O(N ^ 2)
The worst-case Scenario for Quicksort occur when the pivot at each step consistently results in highly unbalanced partitions. When the array is already sorted and the pivot is always chosen as the smallest or largest element. To mitigate the worst-case Scenario, various techniques are used such as choosing a good pivot (e.g., median of three) and using Randomized algorithm (Randomized Quicksort ) to shuffle the element before sorting. - Auxiliary Space: O(1), if we don’t consider the recursive stack space. If we consider the recursive stack space then, in the worst case quicksort could make O ( N ).
Advantages of Quick Sort:
- It is a divide-and-conquer algorithm that makes it easier to solve problems.
- It is efficient on large data sets.
- It has a low overhead, as it only requires a small amount of memory to function.
- It is Cache Friendly as we work on the same array to sort and do not copy data to any auxiliary array.
- Fastest general purpose algorithm for large data when stability is not required.
- It is tail recursive and hence all the tail call optimization can be done.
Disadvantages of Quick Sort:
- It has a worst-case time complexity of O(N 2 ), which occurs when the pivot is chosen poorly.
- It is not a good choice for small data sets.
- It is not a stable sort, meaning that if two elements have the same key, their relative order will not be preserved in the sorted output in case of quick sort, because here we are swapping elements according to the pivot’s position (without considering their original positions).
