Quick sort is another sorting algorithm that allows you to sort values using a divide and conquer strategy, similar to the implementation of merge sort.
Just like its name implies, quick sort is relatively more efficient and faster than merge sort for small array size, but gradually lose its efficiency and speed on large array size.
To understand the implementation of quick sort, let’s start with a small example array as follows:
[6, 7, 3, 1, 5]
First, you need to pick one element as the pivot element. This element is usually the first or the last element of the array.
This example will pick the last element, which is 5. The elements of the array will then be sorted according to this pivot element. Elements smaller than 5 will be placed to the left, while larger elements will be placed to the right:
[6, 7, 3, 1, 5]
[3, 1, 5, 6, 7]
Next, you will have to sort the elements on the left side and the right side of the pivot element, with each taking a new pivot value from the sub-arrays. From the example above, this means sorting two sub-arrays: [3, 1] and [6, 7]. During the third iteration, the position of 3 and 1 will be swapped so that the array is completely sorted:
[6, 7, 3, 1, 5]
[3, 1, 5, 6, 7]
[1, 3, 5, 6, 7]
Quick sort algorithm can be implemented recursively or iteratively. Let’s look at the recursive implementation first.
Quick sort using recursive approach
To implement quick sort using the recursive approach, you need to first create a partitioning() function that accepts the array (arr) you wish to sort, the startIndex, and the endIndex of the array. The function will start by grabbing the pivot element and compare the array elements with itself:
function partition(arr, startIndex, endIndex) {
const pivotVal = arr[endIndex]; // the pivot element
}
Then, you need to keep track of the array index, which will take its value from the startIndex. Each time a swap happens, the index will move until it reaches the middle:
function partition(arr, startIndex, endIndex) {
const pivotVal = arr[endIndex]; // the pivot element
let index = startIndex;
}
It’s time to create the swapping algorithm. Let’s use a for loop to iterate through the array from the startIndex to the endIndex. Each time an element is smaller than the pivotVal element, you swap that element with the index, then move the index up by one:
function partition(arr, startIndex, endIndex) {
const pivotVal = arr[endIndex]; // the pivot element
let index = startIndex;
// begin iterate and swap
for (let i = index; i < endIndex; i++) {
if (arr[i] < pivotVal) {
[arr[i], arr[index]] = [arr[index], arr[i]];
index += 1;
}
}
}
The swapping code above uses destructuring assignment to swap the elements. The logic happens as follows:
let a = 3;
let b = 10;
[a, b] = [b, a];
console.log(a, b); // a=10 b=3
The final step is to move the pivotVal element to the current index, because you need to place the pivot element in the middle of the array. After you move the pivotVal, return the middle index, so that the sorting process can use the middle index to split the array to the left side and the right side:
function partition(arr, startIndex, endIndex) {
const pivotVal = arr[endIndex]; // the pivot element
let index = startIndex;
// begin iterate and swap
for (let i = index; i < endIndex; i++) {
if (arr[i] < pivotVal) {
[arr[i], arr[index]] = [arr[index], arr[i]];
index += 1;
}
}
// move `pivotVal` to the middle index and return middle index
[arr[index], arr[endIndex]] = [arr[endIndex], arr[index]];
return index;
}
With the partition() function done, now you need to create the quickSort() function. This function will simply call the partition() function, passing along the startIndex and endIndex
function quickSort(arr, startIndex, endIndex) {
// Base case or terminating case
if (startIndex >= endIndex) {
return;
}
// Returns midIndex / pivot index
let midIndex = partition(arr, startIndex, endIndex);
// Recursively apply the same logic to the left and right subarrays
quickSort(arr, startIndex, midIndex - 1);
quickSort(arr, midIndex + 1, endIndex);
}
And just like that, the quickSort() function is done. You can test the function by sending an array along with the startIndex and endIndex, which starts from 0 and array.length - 1:
let arr = [-2, 4, 6, 3, 7, 2];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-2, 2, 3, 4, 6, 7]
Here’s the full code:
function partition(arr, startIndex, endIndex) {
const pivotVal = arr[endIndex]; // the pivot element
let index = startIndex;
// begin iterate and swap
for (let i = index; i < endIndex; i++) {
if (arr[i] < pivotVal) {
[arr[i], arr[index]] = [arr[index], arr[i]];
index += 1;
}
}
// move `pivotVal` to the middle index and return middle index
[arr[index], arr[endIndex]] = [arr[endIndex], arr[index]];
return index;
}
function quickSort(arr, startIndex, endIndex) {
// Base case or terminating case
if (startIndex >= endIndex) {
return;
}
// Returns midIndex / pivot index
let midIndex = partition(arr, startIndex, endIndex);
// Recursively apply the same logic to the left and right subarrays
quickSort(arr, startIndex, midIndex - 1);
quickSort(arr, midIndex + 1, endIndex);
}
let arr = [-2, 4, 6, 3, 7, 2];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-2, 2, 3, 4, 6, 7]
Now that you know how to implement quick sort using JavaScript, it’s time to understand the time and space complexity of quick sort in Big O Notation.
The efficiency of quick sort
The quick sort time complexity for the best-case is O(logN) while the worst-case end up at O(n²). The Big O Notation always selects the worst-case as the measurement, so quick sort is not faster than merge sort in terms of time complexity.
Still, the quick sort used in-place algorithm to swap the elements, resulting in O(N) in space complexity. Quick sort only needs extra space for storing the recursive calls.