Quick Sort Algorithm With JavaScript - All You Need To Know Explained
Tags: javascript, tutorial, algorithms, beginners
Published: 2022-01-19 21:55:18

## Introduction
Sorting is something we do everyday because it organises our environment and makes work easy. This is the same with solving problems programmatically. Sorting is done to give the user very good experience while using an application.

There are a couple of ways to sort. This includes bubble sort, heap sort, insertion sort, selection sort, quick sort and so on. 

This article's aim is to explain in detail one of these sorting algorithms. It is the **Quick Sort**.

### Table of Content
1. [What is Quick Sort](#1)
2. [Terminologies](#2)
3. [How Quick Sort Works](#3)
4. [Technically, Quick Sort follows the below steps](#4)
5. [Analysis of Quick Sort's Time Complexity](#5)
6. [How best to pick a pivot](#6)
7. [Implementation of Quick Sort](#7)
8. [Prerequisite](#8)
9. [Method 1](#9)
10. [Method 2](#10)

<a name="1"></a>
## What is Quick Sort
This is a sorting algorithm that takes a group of items, picks a pivot item from the group and compares the pivot item with other items. 

If an item is found to be less than the pivot element, it is moved to the left of the pivot. However, if an item is found to be greater than the pivot, it is moved to the right. This partitions or divides the group into 2.

This process is repeated on each partition until every item is found in its sorted position. It can be said that it uses a divide and conquer approach of solving problems.

> A little confusing? Don't worry. I will break things down. Let us clarify a few terms.

![Calm Down](https://media.giphy.com/media/RnGfXNxCiaCscbOiUU/giphy.gif)

<a name="2"></a>
### Clarification of Terms
Let's explain the following terms to help us understand the definition of quick sort above.
1. Sorted Position 
2. Divide and Conquer  
3. Pivot

**Sorted Position:** 
An item is said to be in a sorted position if it is greater than all elements at it's left and it is less than all element at it's right.

For example, in the image below, **3** is in the sorted position.

![Sorted Position](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5xsovl8rwdze9ukwqu9o.png)

**Divide and Conquer:** 
This is a programming method that takes a problem and continues to break it down until it gets to the smallest solvable problems. It then solves each of this smaller problems and combines the solutions to form a solution to the initial problem.

For example, let's say you are _hungry and needs to eat_. To solve that problem, you will need to divide the initial problem and conquer (solve) other smaller problems like going to the kitchen to cook, dishing out the food, putting it in your mouth until you are satisfied. By the end of these processes, you will have solved the initial problem - **You are hungry and needs to eat**

> That is divide and conquer

**Pivot:** 
The pivot is the element chosen at any point of the sorting to use in comparing other elements. It is not constant. As soon as the current pivot finds its sorting position, another item will be picked in the next partition until all items are in their sorted position.

A pivot could be picked at random or a specific position will be used for every partition. Each of this methods have their advantages and disadvantages as we will see when discussing the time complexity of quick sort.

> Now that we have explained those confusing terms, the definition of Quick Sort should be clearer. I will still go ahead to give you a pictorial representation or description of what we are talking about 


<a name="3"></a>
### How Quick Sort Works Using Pictorial Description   
We will now look at how quick sort works using pictures and this will also give us an idea of how it should be programmed.

So let's say we have a group of numbers (5, 2, 1, 6, 4, 3) and we want to sort it using the Quick sort algorithm. We will use the following steps:

1.. We pick a pivot. Like explained earlier, we can pick any of those elements or numbers as the pivot. Let's pick the the first number - **5**

![Pivot is 5 for first iteration](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pn5xhx54pp3sqgnb2r2n.png)

2.. Set 2 pointers (i and j) at the second index and last index respectively

![Set 2 pointers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cp8ryuo3f7j6a710u5d3.png)

3.. Pointer **i** will be incremented or moved forward while pointer **j** will be decremented or moved backwards 

![Pointer Movement](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y7kc4qbnqljf21yk4jjl.png)

4.. Move **pointer i** until you get to an index with a number greater than the pivot (i.e. 5); then move **pointer j** until you get a number less than pivot. When you have done that, swap the position of the number at **pointer (index) i** and the position of the number at **pointer j**.

![swap the position of the number at pointer (index) i and the position of the number at pointer j](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5e9naemiqcv9v12697d0.png)

And this will now be the result:
![Result of the first Swap](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kwdwhbnhgr7tiwwcixif.png)

5.. Continue step 4 until, the **index i** becomes greater than **index j**. Stop there! That is the base case.

![the index i becomes greater than index j](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7odtkxbkrd7ejfn4pg6f.png)

6.. Swap the number at **index j** with the **pivot**. 

![Swap the number at **index j** with the **pivot**](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nni67ciudowx3mg5g8rr.png)

> Notice that the all numbers to the left of 5 (i.e. the pivot) is less than 5 and all numbers to the right of 5 are greater than 5. This means that 5 is at its **sorted position**.

7.. Now we have two partitions to the left and to the right of 5 which we are not sure are sorted. We will have to repeat the **step 1 to 6** for each partition until every item finds its sorted position.

> **NOTE:** If a group has just one element or no element, we do not try to sort it.

8.. Put the result of each partition together to form a sorted group of numbers.

![sorted group of numbers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mgszzdzm6rjefwc3529o.png)

<a name="4"></a>
### Technically, Quick Sort follows the below steps:
Step 1 − Make any element the pivot
Step 2 − Partition the array on the basis of pivot
Step 3 − Apply Step 1 & 2 on the left partition repeatedly
Step 4 − Apply Step 1 & 2 on the right partition repeatedly

<a name="5"></a>
## Analysis of Quick Sort's Time Complexity 
Remember we said that the pivot selected has an impact on the time it takes to run the Quick Sort.

Imagine that we are to sort a sorted list like so:
![sorted list](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n84yx2kje22zqd2m58xc.png)

If we pick the first item as the pivot for each partition, it will result in the worse case with a time complexity of O(n^2). This is because, the partition will always be done at the pivot index.

![worse case with a time complexity of O(n^2)](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0by4gwy5od6g24i7c2py.png)

If we pick the item at the middle of the list, it will result in the best case with time complexity of O(nlogn). This is because the partition will always be done at the middle.

![best case with time complexity of O(nlogn)](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/699ihvnbd2w9sydotai4.png)

However, achieving best case is very difficult. It requires that the list be sorted and there is one middle element in the middle. So the length of any given list has to be an odd number.

<a name="6"></a>
### How best to pick a pivot
Having come to understand the time complexity issue surrounding quick sort, the 2 ways recommended to pick a pivot are:

1. Pick the element in the middle. If there are two elements in the middle, pick any of them.
2. Pick elements randomly.

We will be sticking with the first one for the purpose of this article. Let's now implement all we have been learning with code.

<a name="7"></a>
## Implementation of Quick Sort

<a name="8"></a>
### Prerequisite
For you to follow through this part onwards, you require [basic understanding of programming](https://www.tutorialspoint.com/computer_programming/computer_programming_basics.htm). 

We are going to be using JavaScript for the implementation. So you can also check that out [here](https://developer.mozilla.org/en-US/docs/Web/JavaScript).

I am going to be using the Replit Playground to write and test my code. You can check it out [here](https://replit.com/). Otherwise, feel free to use what you already know to compile JavaScript.

<a name="9"></a>
### Method 1
This method follows strictly the steps we highlighted above. We will need two functions 
1. The partition function 
2. The Quick Sort function 

**The partition function:**
This function takes 3 parameters (i.e. a list of items, the start index and end index), it then gets the pivot index, swap items and return the left or right index.

Let's do this...

* Create a function named partition
```javascript

function partition(items, leftIndex, rightIndex) {


}

```

* In the function, get the pivot by adding start index (leftIndex) and end index (rightIndex), dividing the answer by 2 and rounding down the answer if it is not a whole number like so:

```javascript

  const pivotIndex = Math.floor((leftIndex + rightIndex) / 2);

```

* Next create a loop to check if the leftIndex is lower than the rightIndex. While this is true, the loop will continue.

```javascript

while (leftIndex <= rightIndex) {

}

```

> While the above loop is true, do the following within the loop:
1.. Check if the item at the leftIndex is less than the item at the pivotIndex. while this is true, increment the leftIndex (i.e. move it rightwards) like so:

```javascript

    while (items[leftIndex] < items[pivotIndex]) {
      leftIndex++;
    }

```

2.. Check if the item at the rightIndex is greater than the item at the pivotIndex. while this is true, decrement the rightIndex (i.e move it leftwards) like so:

```javascript

    while (items[rightIndex] > items[pivotIndex]) {
      rightIndex--;
    }

```

3.. If at any point, the item at the leftIndex is greater than the item at the rightIndex, swap the item at the leftIndex with the item at the rightIndex. Then increment the leftIndex and decrement the rightIndex like so:

```javascript

    if (leftIndex <= rightIndex) {
      [items[leftIndex], items[rightIndex]] =[items[rightIndex], items[leftIndex]];

      leftIndex++;
      rightIndex--;
    }

```
> Outside the loop, assuming that `leftIndex <= rightIndex` is now false, return the leftIndex. This becomes the point of partition.

Our partition function should now look like this:

```javascript

function partition(items, leftIndex, rightIndex) {
  const pivotIndex = Math.floor((leftIndex + rightIndex) / 2);

  while (leftIndex <= rightIndex) {
    while (items[leftIndex] < items[pivotIndex]) {
      leftIndex++;
    }

    while (items[rightIndex] > items[pivotIndex]) {
      rightIndex--;
    }

    if (leftIndex <= rightIndex) {
      [items[leftIndex], items[rightIndex]] = [items[rightIndex], items[leftIndex]];
      leftIndex++;
      rightIndex--;
    }
  }

  return leftIndex;
}

```

**The Quick Sort function:**
With the partition function out of the way, the Quick Sort function is easy. It takes 3 parameters (i.e. a list of items, the start index and end index). Only the first parameter is compulsory. We will follow the next steps:

* Create a function named: quickSort

```javascript

function quickSort(items, leftIndex, rightIndex) {

}

```

* In the function, if the leftIndex is not given, we assign it 0 which is the start index of any array and if the rightIndex is not given, we subtract 1 from the length of the array given and assign the answer to the rightIndex. Here is the code:

```javascript

  leftIndex = leftIndex || 0;
  rightIndex = rightIndex || items.length - 1;

```

* Next, we call upon the partition function to get a pivot for us, swap items and put the pivot in the sorted position. Finally, it returns the point at which to partition the array. See how I do it here:

```javascript

const pivotIndex = partition(items, leftIndex, rightIndex);

``` 

Remember our divide and conquer method? After we get partitions, we will need to do the same thing over and over to those partitions until we get to an array containing just one item or maybe no item.

So we need to keep calling the quickSort function within the quickSort function until there is no more items to sort. That is [recursion](https://www.freecodecamp.org/news/quick-intro-to-recursion/#:~:text=Recursion%20is%20when%20a%20function,unit%20of%20work%20multiple%20times.).

* So if the leftIndex is still less than the end index of the left partition, we call quickSort like so:

```javascript

  if (leftIndex < pivotIndex - 1) {
    quickSort(items, leftIndex, pivotIndex - 1)
  }

```

* If the rightIndex is still greater than the start index of the right partition, we call quickSort like so:

```javascript

  if (rightIndex > pivotIndex) {
    quickSort(items, pivotIndex, rightIndex)
  }

```

* If at any point, both partitions are either empty or contains just one element, then that means that the items are now sorted. At this point, we return the items like so:

```javascript

  return items

```

Our quickSort Function now looks like this:

```javascript

function quickSort(items, leftIndex, rightIndex) {
  leftIndex = leftIndex || 0;
  rightIndex = rightIndex || items.length - 1;

  const pivotIndex = partition(items, leftIndex, rightIndex);

  if (leftIndex < pivotIndex - 1) {
    quickSort(items, leftIndex, pivotIndex - 1)
  }

  if (rightIndex > pivotIndex) {
    quickSort(items, pivotIndex, rightIndex)
  }

  return items
}

```

### Testing 

![GIF Image testing](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lt0zqe1e7674nz60xokj.gif)


![JPEG Image testing](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w15ds1oz9g6kcs1zob8z.png)

Find solution for Method 1 [here](https://replit.com/@EBEREGIT/quick-sort#index.js)

<a name="10"></a>
### Method 2
You will notice that we were keeping a reference to the **start** and **end** index of the partitions in the _Method 1_. But how about if we do not want to do that?

This second method answers that question. Instead of keeping such reference, we can do the following:
1. Terminate the execution if the array of items contains just one item or is empty.
2. If there are more than one item, do the following steps:

* Pick a pivot item.
* Create two (2) temporary arrays. One to hold items less than the pivot and the other to hold items greater than the pivot.
* Loop through the array of items given. if an item is less than the pivot, push it into the left array and if an item is greater than the pivot, push it into the right array. 

*This puts the pivot in its sorted position and creates 2 partitions*

* Repeat the steps above until every item is at its sorted position 
* Then return the new sorted array.

**See code below. I have added comments to make it easy to understand:**

```javascript

function quickSort(items) {
  // terminate execution and return array if empty 
  // or containing one elemrnt
  if (items.length <= 1) return items;

  // set the pivot to the last item on the list
  const pivot = items[items.length - 1];

  // create temporary contaners
  const leftItems = [];
  const rightItems = [];

  // loop through the array to put the pivot in its sorted position 
  for (const item of items.slice(0, items.length - 1)) {
    if (item > pivot) {
      rightItems.push(item)
    } else {
      leftItems.push(item)
    }
  }

  // repeat same processes above on both partition 
  // until every item is at its sorted position
  return [...quickSort(leftItems), pivot, ...quickSort(rightItems)]
}

```

### Testing

![Testing Method 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w487a7rex5oivu1j0uix.png)

Find solution for Method 2 [here](https://replit.com/@EBEREGIT/quickSortClean#index.js)

### Conclusion
It's been an awesome ride with you. Starting from the definition of quick sort, we were able to clarify some terms that might be confusing and we went ahead to use pictorial descriptions to explain further what quick sort is and how it works.

After examining the time complexity, we used one of the suggested ways of implementation to create the quick sort algorithm using JavaScript. Finally, we tried our hands on another method of implementing it.

Quick sort is one of the fastest and most popular sorting algorithms we have out there. It is the method used to implement sorting method provided by most programming languages.

So I want you to try out other methods of implementation and share with me. Looking forward to hearing from you.