Brushing up on data structures and sorting algorithms is a big part of interview prep for software engineers. Among sorting algorithms, quicksort is a must-learn technique. This article will cover all the basics to help you review:
What Is Quicksort?
How Quicksort Works (With Pseudocode)
Quicksort Algorithm
Quicksort Code
Quicksort Complexity
Advantages of Quicksort
Disadvantages of Quicksort
Quicksort FAQs
What Is Quicksort?
Quicksort is one of the most efficient and commonly used sorting algorithms. It is a divide-and-conquer algorithm. It’s also an in-space algorithm as it does not use any extra space for sorting the input data, unlike the merge sort algorithm.
And don’t worry when you hear someone say “Partition Exchange Sort” — it’s just another name for quicksort.
Quicksort is used in:
Commercial computing: Various government and private organizations use quicksort. For example: for sorting students profiles by student name or enrolment number; for sorting employee profiles by employee ID; for sorting transactions by time or date
Information searching: It is widely to make searching of information faster and better
Numerical computations and scientific research: Many efficiently developed algorithms use quicksort for sorting data
How Quicksort Works
Quicksort works by dividing a large array into smaller arrays and then sorting those smaller arrays. A pivot element is used to partition a large array into smaller arrays; smaller arrays are divided recursively until an array with only one or no elements is created.
Quicksort implementation requires two main methods:
quickSort(): Selects a pivot element, partitions the array around the pivot element, and recursively sorts the partitioned subarrays.
partition(): Assigns the pivot element and places the pivot element at its right position in the sorted array. Then, it places all smaller elements to the left of the pivot and places all larger or equal elements to the pivot’s right.
There are several different ways of array partitioning and pivot selection. We’ll cover these in the following sections.
Different Methods of Partitioning the Array
Lomuto Partition Scheme
Lomuto partition scheme selects a pivot element, which is typically the last element of the array. While partitioning a range [start, end], the algorithm maintains index i as it scans the array.
Necessary swaps are made to ensure that after every iteration:
The elements from index “start” to i-1 (inclusive) contain the numbers smaller than the pivot
The elements from index i through the last scanned number (inclusive) are equal to or larger than the pivot
Quicksort Pseudocode Using Lomuto Partition Scheme
algorithm quicksort(A, start, end) is
if start < end then
pi = partition(A, start, end)
quicksort(A, start, pi - 1)
quicksort(A, pi + 1, end)
algorithm partition(A, start, end) is
pivot = A[end]
i = start - 1
for j = start to end do
if A[j] < pivot then
i = i + 1
swap A[i] with A[j]
swap A[i+1] with A[end]
return i+1
Hoare Partition Scheme
Hoare partition scheme uses two pointers — start and end. “start” is assigned the leftmost index, and “end” is assigned the rightmost index of the current partition. Both pointers move towards each other until a wrong pair is encountered. By a wrong pair, we mean:
A pair consisting of an element greater than or equal to pivot at the first pointer ...
… and an element smaller than or equal to pivot at the second pointer
The elements of the wrong pair are then swapped. This continues until “start” and “end” meet each other.
In the Hoare partition scheme, you can choose any element of the array as the pivot. But selecting the last element as the pivot is mostly avoided because it may lead to infinite recursion. For example, if the given array is {2, 9, 6, 11} and pivot is arr[end], then the returned index will always be equal to end, and a call to the same quickSort method will be made infinite times.
Note: In this scheme, the pivot’s final location is not necessarily at the returned index, and the subsequent two partitions that the quickSort recurs on are (start to Pi) and (Pi+1 to end) as opposed to (start to Pi-1) and (Pi+1 to end hi) as in Lomuto’s scheme.
Quicksort Pseudocode Using Hoare Partition Scheme
algorithm quicksort(A, start, end) is
if start < end then
Pi = partition(A, start, end)
quicksort(A, start, pi)
quicksort(A, pi + 1, end)
algorithm partition(A, start, end) is
pivot := A[ floor((start + end) / 2) ]
i = start - 1
j = end + 1
Start loop
do
i = i + 1
while A[i] < pivot
do
j = j - 1
while A[j] > pivot
if i ≥ j then
return j
swap A[i] with A[j]
Different Methods of Selecting the Pivot Element
Select the leftmost element
Select the rightmost element
Select a random element
Select the middle index
Select the median of the first, middle and last element
Algorithm With Example
In this article, we will be using the Lomuto partition scheme, as it is more compact and easy to understand. You can use the Hoare partition scheme if you want a more efficient approach.
We will be selecting the rightmost element as the pivot.
Steps:
Step 1: Select a pivot element
Step 2: Partition the array around the pivot element. Move all the elements < pivot to the left of the pivot and move all elements >= pivot to the pivot’s right
Step 3: After Step 2, the pivot element is in its correct position
Step 4: Apply the quicksort recursively on the left partition
Step 5: Apply the quicksort recursively on the right partition
Step 6: Stop the recursion when the base case is reached. The base case is an array of size zero or one
We’ve used Java to demonstrate the code. Use this as a reference to code in C, C++, Python, or any programming language of your choice.
public class QuickSortIK {
// main method
public static void main(String[] args)
{
// sample array
int arr[] = { 2, 11, 9, 4, 13, 5 };
int start = 0;
int end = arr.length - 1;
// printing the original array
System.out.print("Original array - ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
// sorting the array using quickSort
quickSort(arr, start, end);
System.out.println();
// printing the array after sorting
System.out.print("Array after sorting - ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// this method divides the large array into
// smaller arrays
private static void quickSort(int[] arr, int start,
int end)
{
if (start < end) {
// Pivot element around which the array will be
// partitioned
int pivot = partition(arr, start, end);
// Recursively calling quickSort on elements
// to the left of the pivot element
quickSort(arr, start, pivot - 1);
// Recursively calling quickSort on elements
// to the right of the pivot element
quickSort(arr, pivot + 1, end);
}
}
// this method makes the end element the pivot
// element and places pivot element at its right position in
// the sorted array and places all smaller elements to the
// left of the pivot and places all larger elements to the
// right of the pivot
private static int partition(int[] arr, int start,
int end)
{
// making element present at the end index in arr
// the pivot element
int pivot = arr[end];
int i = (start - 1);
for (int j = start; j <= end - 1;
j++) { // checking if current element is
// smaller than pivot or not
if (arr[j]
< pivot) { // if current element is smaller
// increment i
// and swap with arr[j]
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, end);
return (i + 1);
}
private static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Output:
Original array - 2 11 9 4 13 5
Array after sorting - 2 4 5 9 11 13
Quicksort Code Explained
1. Sorting the Original Array
arr[] = {2, 11, 9, 4, 13, 5}
start = 0, end = 5, pivot = arr[end] ={5}
i = (start - 1) = -1 (index of smaller element), j = 0 (loop variable)
Traverse elements from start to end
Pass 1:
j = 0
i = 0
Since arr[j] < pivot, i++ and swap (arr[i], arr[j] )
arr[] = {2, 11, 9, 4, 13, 5} // no change as arr[i] = arr[j] = 2
Pass 2:
j = 1
i = 0:
Since (arr[j] > pivot) //no change
arr[] = {2, 11, 9, 4, 13, 5}
Pass 3:
j = 2
i = 0:Since (arr[j] > pivot) //no change
arr[] = {2, 11, 9, 4, 13, 5}
Pass 4:
j = 3
i = 1
Since arr[j] < pivot , i++ and swap (arr[i], arr[j])
i = (start - 1) = -1 (index of smaller element), j = 0 (loop variable)
Pass 1:
i=-1
j=0
Since arr[j] < pivot , i++ and swap (arr[i], arr[j])
arr[] = {2, 4, 9, 11, 13, 5} // no change as arr[i] = arr[j] = 2
j = 1 > end -1. So swap arr[i+1] and pivot
arr[] = {2, 4, 5, 9, 13, 11} // no change as arr[i+1] = pivot = 4
Now, quickSort will not make this recursive call further because the left partition contains only one element (2) and the right partition contains no elements; there is no element greater than 4 between indices start = 0 to end = 1.
3. Sorting the Right Partition Form First Recursive Call
quickSort will not recursively sort the left partition further because it does not contain any element; there is no element less than 9 between indices start = 3 to end = 5.
So, let's sort the right partition of this recursive call:
arr[] = {2, 4, 5, 9, 13, 11}
start = 4, end = 5, pivot = arr[end] ={11}
i = 3(index of smaller element), j = 4 (loop variable)
Let’s assume that the array to be sorted has n elements.
Best case:O(n*logn) This happens if we pick the median of the array as the pivot element every time. The size of subarrays will be half the size of the original array. In this case, the time taken will be O(n*logn).
Worst case:O(n^2) This happens if we pick the largest or the smallest element of the array as the pivot element every time. The size of the subarray after partitioning will be n-1 and 1.
Average case:O(n*logn) This is the average time taken for all n! permutations of n elements.
Space Complexity
Quicksort is a recursive algorithm, and the space complexity depends on the size of the recursive tree. A stack is used to store the recursive tree.
Best case:O(logn) This happens when the pivot element’s correct position in the partitioned array is at the middle every time. The size of subarrays will be half the size of the original array. In this case, the recursive tree’s size will be O(log(n)).
Worst case:O(n) This happens when the pivot element is the largest or smallest element of the array in every recursive call. The size of the subarray after partitioning will be n-1 and 1. In this case, the size of the recursive tree will be n.
Advantages of Quicksort
Is in-place, as it uses only a small auxiliary stack
Requires only n (log n) time to sort n items on an average case
Disadvantages of Quicksort
Is recursive; if recursion is not available, quicksort implementation is extremely complicated
Requires quadratic (i.e., n^2) time in the worst case
Is not stable
Quicksort FAQs
Question 1: Which is better — merge sort or quicksort?
Answer: Quicksort is an in-space sorting algorithm as it doesn’t require any additional space to sort the given array. On the other hand, merge sort requires an auxiliary array to merge the sorted sublists. Hence, we can say that the quicksort has an advantage over the merge sort in terms of space.
Question 2: Is quicksort a stable sorting algorithm?
Answer: Efficient implementation of quicksort is not stable because it swaps non-adjacent elements, and the relative order of equal array elements may change. For example, suppose there are two 5s in the array. Let's call the first 5 “5a” and the second one “5b”. After sorting, 5b can be at a lower index than 5a. In this article, we have used the non-stable approach. Quicksort can be made stable, but it will require extra O(n) space.
Are You Ready to Nail Your Next Coding Interview?
Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar.
As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
.png)
