NJOKU SAMSON EBERE

Posted on Jan 19, 2022 • Edited on Jan 24, 2022

Quick Sort Algorithm With JavaScript - All You Need To Know Explained

#javascript #tutorial #algorithms #beginners

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

What is Quick Sort
Terminologies
How Quick Sort Works
Technically, Quick Sort follows the below steps
Analysis of Quick Sort's Time Complexity
How best to pick a pivot
Implementation of Quick Sort
Prerequisite
Method 1
Method 2

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.

Clarification of Terms

Let's explain the following terms to help us understand the definition of quick sort above.

Sorted Position
Divide and Conquer
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.

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

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

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

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

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.

And this will now be the result:

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

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

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.

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

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:

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.

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.

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.

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:

Pick the element in the middle. If there are two elements in the middle, pick any of them.
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.

Implementation of Quick Sort

Prerequisite

For you to follow through this part onwards, you require basic understanding of programming.

We are going to be using JavaScript for the implementation. So you can also check that out here.

I am going to be using the Replit Playground to write and test my code. You can check it out here. Otherwise, feel free to use what you already know to compile JavaScript.

Method 1

This method follows strictly the steps we highlighted above. We will need two functions

The partition function
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.




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:




    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:




    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:




    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:




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




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:




  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:




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.

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




  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:




  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:




  return items

Our quickSort Function now looks like this:



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

Find solution for Method 1 here

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:

Terminate the execution if the array of items contains just one item or is empty.
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:



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

Find solution for Method 2 here

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.