Quick Sort in JavaScript

Quick Sort, devised by Tony Hoare in 1959, leverages the divide-and-conquer strategy. It selects a pivot element and then arranges all smaller elements to one side and larger ones to the other.

Quick Sort Under the Hook

Quick Sort operates in three steps:

1. Selecting a pivot.

2. Shifting elements smaller than the pivot to one side, and moving elements larger than the pivot to the other side.

3. Repeating these steps for both sides separately.

Consider, for instance, sorting [3, 9, 4, 7, 5, 1, 6, 2, 8] with 7 as the pivot. After one round, it becomes [3, 4, 5, 1, 6, 2, 7, 9, 8]. The pivot 7 is correctly placed, and we can then divide the array into two parts: [3, 4, 5, 1, 6] and [9, 8], which can be sorted separately.

Quick Sort Implementation in JavaScript : Partition

Let's implement Quick Sort in JavaScript. First, we partition the array around the pivot in our partition function:

In this portion of the code, we selected the last element as the pivot and placed smaller elements on the left. The function starts by initialising i to one index before the start. This basically keeps track of the latest position where an element has been swapped because it was less than or equal to the pivot. If arr[j] is less than or equal to the pivot, i is incremented, and then arr[j] is swapped with arr[i]. Essentially, smaller elements get pushed towards the front of the array (or the given part of the array).

The start and end parameters control which part of the given array is under the partition operation. Using these parameters, we can apply partition to some part of the array, which will be helpful later.

Quick Sort Implementation in JavaScript : Sorting

Then, we apply Quick Sort with a function that invokes partition and recursively sorts the two halves:

Spot on! We've just created a fully functioning Quick Sort algorithm in JavaScript.

Honing In On Quick Sort Efficiency

The time complexity of Quick Sort can vary. Generally speaking, the more unique items there are, the quicker Quick Sort works. In the best and average cases, it shines with a time complexity of O(n∗log(n)). However, the time complexity can degrade to O(n2) in the worst case.