↓Skip to main content

Understand Quicksort the easy way

·6 mins
Table of Contents

Photo by Iñaki del Olmo on Unsplash

Data structures and Algorithms are the key skills for a software developer. Recently when I was preparing for a job change, learning sorting algorithms was not smooth.
The theory is simple and straight but its implementation is just the opposite.

I think concept and implementation are inversely proportional. 🤔

There are many sorting algorithms like bubblesort, mergesort, quicksort etc. Among all, quicksort is one of the most popular sorting algorithms.

Today, I’ll try to put all my learning while learning the quicksort.

What is Quicksort? #

Quicksort is one of the efficient sorting algorithms and the average complexity is O(n log n).
There are only 3 worst cases when its complexity is O(n^2).

  1. Array is sorted [2,3,4]
  2. Array is reverse sorted [4,3,2]
  3. All elements are identical in the array [4,4,4]

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. – Wikipedia

How quicksort works? 🤔 #

Gif by Wikimedia

Quicksort works on the divide and conquer algorithm.

Select any element in the array and this element is known as pivot.
Quicksort is all about finding the correct position(index) of this pivot in the array.
Elements less than pivot must be in the left side of the pivot and elements greater than the pivot must be in the right side of the pivot.

Example explains better 😉 #

We have an array

[3, 6, 2, 5, 4, 1, 7];

Any element can be selected as a pivot.
For this example, the first element of the array is the pivot ⚓

The pivot is 3

pivot: 3, [3, 6, 2, 5, 4, 1, 7];

Elements less than pivot: 2, 1
Elements greater than pivot: 6, 5, 4, 7

Move the elements less than pivot to the left side of pivot and elements greater than pivot to the right side of the pivot. Now, the correct position of the pivot (3) in the array is at index 2.

[2, 1, 3, 6, 5, 4, 7];

Once, the pivot is in the correct position, divide the array. The elements on the left and the right side of the pivot will be the sub-array.

[2, 1, 3, 6, 5, 4, 7];
       ^ last pivot at the correct position
[2, 1]   [6, 5, 4, 7];

Sub-array 1: [2, 1]
Sub-array 2: [6, 5, 4, 7]

Sub-array 1 #

Select the first element 2 as pivot.

pivot: 2, [2, 1];

Elements less than the pivot: 1
Elements greater than the pivot: No elements

Again, move the elements less than pivot to the left side of pivot and elements greater than pivot to the right side of the pivot. The correct position of the pivot (2) in the sub-array is at index 1.

[1, 2];

Now, again divide the array. Elements on the left side and the right side will be sub-array.

There is no need to create a sub-array if there is only 1 element in the sub-array. It means pivot is already at the correct position in the array.

Sub-array 2 #

Select the first element 6 as pivot.

pivot: 6, [6, 5, 4, 7];

Elements less than the pivot: 5, 4
Elements greater than the pivot: 7

Again, move the elements less than pivot to the left side of pivot and elements greater than pivot to the right side of the pivot. The correct position of the pivot (6) in the sub-array is at index 2.

[5, 4, 6, 7];

Now, again divide the array. Elements on the left side and the right side of the pivot will be sub-array.

Sub-array 21: [5, 4]
Sub-array 22: [7]

We have to keep dividing the array by the time all the pivot will be on its correct index.

After finding the correct position of pivot in sub-array 21

[4, 5];

The final array with all its pivot at the correct position.

[1, 2, 3, 4, 5, 6, 7];

Now, we understood the quicksort’s process, let’s implement it in javascript.

JS implementation #

The process has the following steps:

  1. Select the pivot.
  2. The elements less than the pivot and the elements greater than the pivot, move them to the left side and the right side of the pivot respectively.

Step 1 #

Select the first element of the array as pivot.

❗ Pivot can be any element of the array. Step 2 may vary to how the pivot is selected.

Step 2 #

To move the elements on the left and the right side of the pivot.

i: Start from the leftmost element and its index is i.
j: Start from the rightmost element or the last element of the array and its index is j.

Whenever an element at index i is greater than the pivot and element at index j is smaller than the pivot, swap the elements at index i and j.

If, index i cross-index j then stop there and swap the element at j index with the pivot.

The index j is the sorted position of the pivot in the array.

The complete code is available on gist. js and golang implementation.

/**
* ********************************** Quick Sort ***********************************************
* UNSORTED ARRAY [3, 7, 8, 5, 2, 1, 9, 6, 4]
* pivot ^
* pivot: 3 arr: [ 2, 1, 3, 5, 8, 7, 9, 6, 4 ]
* [2, 1] [5, 8, 7, 9, 6, 4 ]
* pivot ^ ^
* pivot: 2 arr: [ 1, 2 ]
* pivot: 5 arr: [ 4, 5, 7, 9, 6, 8 ]
* [ 4] [7, 9, 6, 8 ] --> Array with single element is sorted
* pivot ^
* pivot: 7 arr: [ 6, 7, 9, 8 ]
* [ 6] [9, 8 ]
* pivot ^
* pivot: 9 arr: [ 8, 9 ]
*
* SORTED ARRAY [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
* *********************************************************************************************
*
* Worst-case Performance: O(n^2)
* Best-cae Performance: O(n log n)
* Average Performance: O(n log n)
*
* ********************************** Quick Sort ***********************************************
*/
/**
* quicksort - Sort the array using quicksort method
* @param {Array} arr
*/
const quicksort = arr => {
// return the array if array length is 1 or less than 1
if (arr.length <= 1) {
return arr;
}
// make the first element as pivot
const pivot = arr[0];
// i will move in right direction (away from pivot) from index position 1
let i = 1;
// j will move in left direction (towards pivot) from the last element of the array
let j = arr.length - 1;
// iterate till i and j are not passed each other
while (i < j) {
// find the value which is larger than pivot
while (arr[i] < pivot && i < arr.length) {
i++;
}
// find the value which is lesser than pivot
while (arr[j] > pivot && j > 0) {
j--;
}
// if i is less than j
// swap the value at i and j index
// swap the larger value at i with lesser value at j
if (i < j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap the value at j with pivot
// j index is the sorted position of the pivot
// everything to its left is lesser and larger to its right.
let temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
console.log("pivot: ", pivot, "arr: ", arr);
// left side of the pivot will be a new subarray
let left = arr.slice(0, j);
// if the length of the subarray is greater than 1
// then quicksort the subarray
if (left.length > 1) {
left = quicksort(left);
}
// right side of the pivot will be a new subarray
let right = arr.slice(j + 1, arr.length);
// if the length of the subarray is greater than 1
// then quicksort the subarray
if (right.length > 1) {
right = quicksort(right);
}
// console.log(left.concat(pivot, right));
// concat all the elements of the array
// left pivot and right
// return the sorted array
return left.concat(pivot, right);
};
console.log(quicksort([3, 7, 8, 5, 2, 1, 9, 6, 4]));
/**
* OUTPUT
*
* pivot: 3 arr: [ 2, 1, 3, 5, 8, 7, 9, 6, 4 ]
* pivot: 2 arr: [ 1, 2 ]
* pivot: 5 arr: [ 4, 5, 7, 9, 6, 8 ]
* pivot: 7 arr: [ 6, 7, 9, 8 ]
* pivot: 9 arr: [ 8, 9 ]
*
* SORTED ARRAY - [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
*/
view raw quicksort.js hosted with ❤ by GitHub

💡 Roll up your sleeves

  • Line 33: Check the length of the array. If the length of the array is 1 or less than one, return the array as it is. It means the array is already in sorted order.
  • Line 38: Select the first element as the pivot.
  • Line 41: Initialize index i to 1 as it is the leftmost element of the array.
  • Line 44: Initialize index j to arr.length-1, the last index of the array as it is the rightmost element of the array.
  • Line 47: Iterate till index i do not cross-index j.
  • Line 49: Iterate index i till value at index i is larger than the pivot. i will move away from the pivot, from index 1 to the last index of the array.
  • Line 54: Iterate index j till value at index j is smaller than the pivot. j will move towards the pivot, from the last index of the array to the index 1.

  • Line 61-65: If index i is less than j (didn’t cross each other), then swap the value at index i and at index j.
  • Line 71-73:: Index j is the sorted position of the pivot. Swap the value at index j with the pivot.

Now, the pivot is sorted in the array. The array on the left and the right side of the pivot is still unsorted. Create 2 sub-arrays. A left side of the pivot is one sub-array and right side of the pivot is another sub-array.

  • Line 78: Use slice to create the left-side sub-array. slice(indexFrom, indexTo-1). The to range is not inclusive. If slice is slice(0,5), then its range is [0-4].
  • Line 82: Check if the left-subarray length is greater than 1. If true, then recursively call quicksort and pass left-subarray as an argument.
  • Line 87: Use slice to create the right-side sub-array.
  • Line 91: Check if the right-subarray length is greater than 1. If true, then recursively call quicksort and pass right-subarray as an argument.
  • Line 100: Return the sorted array. Concat the left-subarray, the pivot element and the right-subarray.

A recursive function is a function that calls itself until a predefined condition satisfy.

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. – wikipedia

References #

↑