# Implementing quick sort in JavaScript

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.

### Take your skills to the next level ⚡️

I'm sending out an occasional email with the latest tutorials on programming, web development, and statistics. Drop your email in the box below and I'll send new stuff straight into your inbox!

No spam. Unsubscribe anytime.