 Practice
Resources
Contests
Online IDE
New
Free Mock
Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
Scaler
Explore Offerings by SCALER ## Welcome to Interviewbit, help us create the best experience for you!

Currently, You are a: College/University *
Enter the name of your college
Branch *
Year of completion * College/University *
Enter the name of your college
Branch *
Year of completion * Current Company *
Enter company name
Experience * ## You're all set! Full name *
Email *

By creating an account, I acknowledge that I have read and agree to InterviewBit’s Terms and Privacy Policy . ## Welcome back!

Email * Go to Problems

Be a Code Ninja!

# QuickSort Algorithm

The algorithm was developed by a British computer scientist Tony Hoare in 1959. The name "Quick Sort" comes from the fact that, quick sort is capable of sorting a list of data elements significantly faster (twice or thrice faster) than any of the common sorting algorithms. It is one of the most efficient sorting algorithms and is based on the splitting of an array (partition) into smaller ones and swapping (exchange) based on the comparison with 'pivot' element selected. Due to this, quick sort is also called as "Partition Exchange" sort. Like Merge sort, Quick sort also falls into the category of divide and conquer approach of problem-solving methodology.

Table of content

### Application

#### Quicksort works in the following way

Before diving into any algorithm, its very much necessary for us to understand what are the real world applications of it. Quick sort provides a fast and methodical approach to sort any lists of things. Following are some of the applications where quick sort is used.

• Commercial computing: Used in various government and private organizations for the purpose of sorting various data like sorting of accounts/profiles by name or any given ID, sorting transactions by time or locations, sorting files by name or date of creation etc.
• Numerical computations: Most of the efficiently developed algorithms use priority queues and inturn sorting to achieve accuracy in all the calculations.
• Information search: Sorting algorithms aid in better search of information and what faster way exists than to achieve sorting using quick sort.

Basically, quick sort is used everywhere for faster results and in the cases where there are space constraints.

### Explanation

Taking the analogical view in perspective, consider a situation where one had to sort the papers bearing the names of the students, by name from A-Z. One might use the approach as follows:

1. Select any splitting value, say L. The splitting value is also known as Pivot.
2. Divide the stack of papers into two. A-L and M-Z. It is not necessary that the piles should be equal.
3. Repeat the above two steps with the A-L pile, splitting it into its significant two halves. And M-Z pile, split into its halves. The process is repeated until the piles are small enough to be sorted easily.
4. Ultimately, the smaller piles can be placed one on top of the other to produce a fully sorted and ordered set of papers.
5. The approach used here is reduction at each split to get to the single-element array.
6. At every split, the pile was divided and then the same approach was used for the smaller piles by using the method of recursion.

Technically, quick sort follows the below steps:
Step 1 − Make any element as pivot
Step 2 − Partition the array on the basis of pivot
Step 3 − Apply quick sort on left partition recursively
Step 4 − Apply quick sort on right partition recursively

### Quick Sort Example:

#### Problem Statement

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).

#### Solution

Step 1:

• Make any element as pivot: Decide any value to be the pivot from the list. For convenience of code, we often select the rightmost index as pivot or select any at random and swap with rightmost. Suppose for two values “Low” and “High” corresponding to the first index and last index respectively.
• In our case low is 0 and high is 5.
• Values at low and high are 50 and 32 and value at pivot is 32.
• Partition the array on the basis of pivot: Call for partitioning which rearranges the array in such a way that pivot (32) comes to its actual position (of the sorted array). And to the left of the pivot, the array has all the elements less than it, and to the right greater than it.
• In the partition function, we start from the first element and compare it with the pivot. Since 50 is greater than 32, we don’t make any change and move on to the next element 23.
• Compare again with the pivot. Since 23 is less than 32, we swap 50 and 23. The array becomes `23, 50, 9, 18, 61, 32`
• We move on to the next element 9 which is again less than pivot (32) thus swapping it with 50 makes our array as `23, 9, 50, 18, 61, 32`.
• Similarly, for next element 18 which is less than 32, the array becomes `23, 9, 18, 50, 61, 32`. Now 61 is greater than pivot (32), hence no changes.
• Lastly, we swap our pivot with 50 so that it comes to the correct position.

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:

1. Sublist before pivot element
2. Sublist after pivot element

Step 4: Repeat the steps for the left and right sublists recursively. The final array thus becomes
`9, 18, 23, 32, 50, 61`.

The following diagram depicts the workflow of the Quick Sort algorithm which was described above. ### Pseudocode of Quick Sort Algorithm:

Quick Sort

``````/**
* The main function that implements quick sort.
* @Parameters: array, starting index and ending index
*/
quickSort(arr[], low, high)
{
if (low < high)
{
// pivot_index is partitioning index, arr[pivot_index] is now at correct place in sorted array
pivot_index = partition(arr, low, high);

quickSort(arr, low, pivot_index - 1);  // Before pivot_index
quickSort(arr, pivot_index + 1, high); // After pivot_index
}
}
``````

Partition Method

``````/**
* The function selects the last element as pivot element, places that pivot element correctly in the array in such a way
* that all the elements to the left of the pivot are lesser than the pivot and
* all the elements to the right of pivot are greater than it.
* @Parameters: array, starting index and ending index
* @Returns: index of pivot element after placing it correctly in sorted array
*/
partition (arr[], low, high)
{
// pivot - Element at right most position
pivot = arr[high];
i = (low - 1);  // Index of smaller element
for (j = low; j <= high-1; j++)
{
// If current element is smaller than the pivot, swap the element with pivot
if (arr[j] < pivot)
{
i++;    // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}``````

### Implementation of Quick Sort

Following are C, C++, Java and Python implementations of QuickSort.

``````Implementation of Quick Sort Algorithm in C:
# include <stdio.h>

// to swap two numbers
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

int partition (int arr[], int low, int high)
{
int pivot = arr[high];  // selecting last element as pivot
int i = (low - 1);  // index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If the current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++;    // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/*
a[] is the array, p is starting index, that is 0,
and r is the last index of array.
*/
void quicksort(int a[], int p, int r)
{
if(p < r)
{
int q;
q = partition(a, p, r);
quicksort(a, p, q-1);
quicksort(a, q+1, r);
}
}

// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

int main()
{
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
int n = sizeof(arr)/sizeof(arr);

// call quickSort function
quicksort(arr, 0, n-1);

printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
``````
``````Quicksort example program in c++:
#include<iostream>
#include<cstdlib>

using namespace std;

// Swapping two values.
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}

// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high)
{
int pivot, index, i;
index = low;
pivot = high;

// Getting index of the pivot.
for(i=low; i < high; i++)
{
if(a[i] < a[pivot])
{
swap(&a[i], &a[index]);
index++;
}
}
// Swapping value at high and at the index obtained.
swap(&a[pivot], &a[index]);

return index;
}

// Random selection of pivot.
int RandomPivotPartition(int a[], int low, int high)
{
int pvt, n, temp;
n = rand();
// Randomizing the pivot value in the given subpart of array.
pvt = low + n%(high-low+1);

// Swapping pivot value from high, so pivot value will be taken as a pivot while partitioning.
swap(&a[high], &a[pvt]);

return Partition(a, low, high);
}

int QuickSort(int a[], int low, int high)
{
int pindex;
if(low < high)
{
// Partitioning array using randomized pivot.
pindex = RandomPivotPartition(a, low, high);
// Recursively implementing QuickSort.
QuickSort(a, low, pindex-1);
QuickSort(a, pindex+1, high);
}
return 0;
}

int main()
{
int n, i;
cout<<"\nEnter the number of data elements to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}

QuickSort(arr, 0, n-1);

// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];

return 0;
}
``````
``````// Java program for implementation of QuickSort
class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;

// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;

return i+1;
}

/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);

// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}

/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}

// Driver program
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;

QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);

System.out.println("sorted array");
printArray(arr);
}
}
``````
``````# Python program for Quicksort
# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr,low,high):
i = ( low-1 )		 # index of smaller element
pivot = arr[high]	 # pivot

for j in range(low , high):

# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:

# increment index of smaller element
i = i+1
arr[i],arr[j] = arr[j],arr[i]

arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )

# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index

# Function to do Quick sort
def quickSort(arr,low,high):
if low < high:

# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr,low,high)

# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)

# Driver code to test above
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]),
``````

### Complexity Analysis

#### Time Complexity of Quick sort

• Best case scenario: The best case scenario occurs when the partitions are as evenly balanced as possible, i.e their sizes on either side of the pivot element are either are equal or are have size difference of 1 of each other.

• Case 1: The case when sizes of sublist on either side of pivot becomes equal occurs when the subarray has an odd number of elements and the pivot is right in the middle after partitioning. Each partition will have `(n-1)/2` elements.
• Case 2: The size difference of 1 between the two sublists on either side of pivot happens if the subarray has an even number, `n`, of elements. One partition will have `n/2` elements with the other having `(n/2)-1`.

In either of these cases, each partition will have at most `n/2` elements, and the tree representation of the subproblem sizes will be as below: The best-case complexity of the quick sort algorithm is O(n logn)

• Worst case scenario: This happens when we encounter the most unbalanced partitions possible, then the original call takes `n` time, the recursive call on `n-1` elements will take `(n-1)` time, the recursive call on `(n-2)` elements will take `(n-2)` time, and so on. The worst case time complexity of Quick Sort would be O(n2). #### Space Complexity of Quick sort

The space complexity is calculated based on the space used in the recursion stack. The worst case space used will be `O(n)` . The average case space used will be of the order `O(log n)`. The worst case space complexity becomes `O(n)`, when the algorithm encounters its worst case where for getting a sorted list, we need to make `n` recursive calls.

### FAQs

• What is the average case run time complexity of Quick Sort?
The average case run time of quick sort is `O(n logn)` . This case happens when we dont exactly get evenly balanced partitions. We might get at worst a 3-to-1 split on either side of pivot element. The proof of this is quite mathematically rigorous and is out of scope of the discussion.

• 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.

• Is Quick Sort an inplace algorithm?
Quick sort is an inplace algorithm which means the numbers are all sorted within the original array itself.

• What is Randomised Quick Sort? Why is it used?

• Sometimes, it happens that by choosing the rightmost element at all times might result in the worst case scenario.
• In such cases, choosing a random element as your pivot at each step will reduce the probability of triggering the worst case behavior. We will be more likely choosing pivots closer to the center of the array, and when this happens, the recursion branches more evenly and thus the algorithm terminates a lot faster.
• The runtime complexity is expected to be `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?

• Auxiliary Space : Quick sort is an in-place sorting algorithm whereas Merge sort uses extra space. In-place sorting means no additional storage space is used to perform sorting (except recursion stack). Merge sort requires a new temporary array to merge the sorted arrays thereby making Quick sort the better option.
• Worst Cases : The worst case runtime of quick sort is O(n2) can be avoided by using randomized quicksort as explained in the previous point. Obtaining average case behavior by choosing random pivot element improves the performance and becomes as efficient as merge sort.
• Cache Friendly: Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.
• 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.

## Serious about Learning Programming ?

Learn this and a lot more with Scaler Academy's industry vetted curriculum which covers Data Structures & Algorithms in depth.
Primers
Examples

## Arrays Problems

Array math
Value ranges
Problem Score Companies Time Status
Max Min 150
17:31
Merge Intervals 225 78:57
Merge Overlapping Intervals 225 48:24
Simulation array
Problem Score Companies Time Status
Perfect Peak of Array 200 48:49
Kth Row of Pascal's Triangle 225
28:32
Spiral Order Matrix II 225 48:40
Pascal Triangle 225 26:46
Anti Diagonals 225 41:46
Bucketing
Problem Score Companies Time Status
Triplets with Sum between given range 200
76:05
Balance Array 200 61:31
Find Duplicate in Array 450 40:13
Maximum Consecutive Gap 450 58:46
Arrangement
Problem Score Companies Time Status
Sort array with squares! 200 31:16
Largest Number 225 70:26
Rotate Matrix 300 60:26
Next Permutation 300 63:13
Find Permutation 300 56:00
Sorting
Problem Score Companies Time Status
Noble Integer 200 43:30
Wave Array 225 22:08
Hotel Bookings Possible 225 66:06
Max Distance 250 68:14
Maximum Unsorted Subarray 250 68:52
Space recycle
Problem Score Companies Time Status
Set Matrix Zeros 300 48:04
First Missing Integer 300 64:38
Maximum Sum Square SubMatrix 300 56:24
Missing / repeated number
Problem Score Companies Time Status
First Missing Integer 300 64:38
Repeat and Missing Number Array 350 63:55
N/3 Repeat Number 600
68:22

Problem Score Companies Time Status
Reorder Data in Log Files 200 42:20
Move Zeroes 200 24:24
Make equal elements Array 200 28:17
Segregate 0s and 1s in an array 200 14:14
Array Sum 200 30:37
Set Intersection 200 60:52
Occurence of Each Number 200 22:32
Greater of Lesser 200 12:03
Spiral Matrix 200 30:23
Product of All 200 29:54
Chips Factory 200 17:43
Greater than All 150 17:04
Pythagorean Triplets 200 22:32
Diagonal Flip 200 16:43
Positive Negative 100 9:33 Free Mock Assessment
Help us know you better for the best experience
Current Employer *
Enter company name