DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Quicksort Algorithm: Explained With Diagrams and Javascript
Bonnie
Bonnie

Posted on

Quicksort Algorithm: Explained With Diagrams and Javascript

Quicksort is a method of sorting values in a list through a repeated procedure to successive lists.

In the Quicksort method, a value is chosen from the main list, and it is named the pivot value. The remaining values are divided into two lists.

  • One list is of values that are less than or equal to the pivot value. Those values go to the left of the pivot value.

  • The second list is of values that are greater than the pivot value. Those values go to the right side of the pivot value.

The Quicksort method is repeated on all resulting lists until only a single or an empty value list remains.

After that, you pick the last single value, and if the value is on the left side of the pivot value, it will stay that way until you get to the first pivot value at the top. The same case remains for the values on the right side of the pivot value.

To make the Quicksort method clear, let us use a diagram.

Let us say you have a list of values as shown in the diagram below.

Image description

What you want to do is to arrange the values from the smallest to largest. How do you do that?

The first thing you are supposed to do is to pick one value and make it the pivot value. Let say you pick 47 and make it the pivot value. The next thing you are supposed to do is place values that are less than or equal to 47 on the left side. Values that are greater than 47 will go to the right.

Here is a diagram that explains it better.

Image description

We will now repeat the same process until only a single or empty list of values remains.

Image description

The next step is to start with the single value lists. Then place the value on the left side of the pivot value if it is already on the left or place it on the right side if it is already on the right side.

Image description

Here is how the final results will look like.

Image description

As you can see from the results, the values have been arranged from the smallest to the largest.

That’s the power of the Quicksort method.

Quicksort Method In Javascript

The first thing we will do here is to define our values variable using const.

const values = [2, 27, 14, 52, 31, 96, 73, 47, 22, 6];
Enter fullscreen mode Exit fullscreen mode

Let us create a function that will be able to Quicksort our list values when we call it. To do that, we will first need to declare our function.

function QuickSort(List) {

}
Enter fullscreen mode Exit fullscreen mode

Our function Quicksort takes one parameter, called List.

The next thing we will do is to check the length of the List. If it is 1, then we will return the list as it is.

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }
}
Enter fullscreen mode Exit fullscreen mode

Let us now select a pivot value and create two empty lists. We will name one list leftList and the other list rightList.

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];
}
Enter fullscreen mode Exit fullscreen mode

As you can see from the code block above, our pivot value will be the last value from our list of values that we defined in our first step.

The two empty lists we created will be used to store values as compared with the pivot value. If a value is less than or equal to the pivot value, it will be stored in the leftList. If a value is greater than the pivot value, it will be stored in the rightList.

To make that happen, we will use a for loop as shown below.

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];

   for (let i = 0; i < List.length - 1; i++) {
       if (List[i] < pivot) {
           leftList.push(List[i]);
       }
       else {
           rightList.push(List[i])
       }
   }
}
Enter fullscreen mode Exit fullscreen mode

Let us call Quicksort on leftList and rightList to partition them so that they can get sorted completely. To be able to do that, we will use Javascript Spread Operator.

The Javascript Spread Operator will allow us to quickly copy all or part of an existing list into another list.

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];

   for (let i = 0; i <= List.length - 1; i++) {
       if (List[i] < pivot) {
           leftList.push(List[i]);
       }
       else {
           rightList.push(List[i])
       }
   }

   return [...QuickSort(leftList), pivot, ...QuickSort(rightList)];
}
Enter fullscreen mode Exit fullscreen mode

To see if our code works, let us call the Quicksort function on our list of values and see if they will be arranged from the smallest to the largest.

const values = [2, 27, 14, 52, 31, 96, 73, 47, 22, 6];

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];

   for (let i = 0; i < List.length - 1; i++) {
       if (List[i] < pivot) {
           leftList.push(List[i]);
       }
       else {
           rightList.push(List[i])
       }
   }

   return [...QuickSort(leftList), pivot, ...QuickSort(rightList)];
}

console.log(QuickSort(values));
Enter fullscreen mode Exit fullscreen mode

To view the results, you need to create a HTML file and link the Javascript file that you have written the code above.

<!DOCTYPE html>
<html lang="en">
<head>
   <meta charset="UTF-8">
   <meta http-equiv="X-UA-Compatible" content="IE=edge">
   <meta name="viewport" content="width=device-width, initial-scale=1.0">
   <title>Document</title>
</head>
<body>

   <script src="/assignment.js"></script>
</body>
</html>
Enter fullscreen mode Exit fullscreen mode

After that, open the HTML file on your browser. Then right click the web page and select Inspect at the bottom from the list of options.

Image description

Then navigate to the console and you should be able to see that our values are arranged from the smallest to the largest.

Image description

Conclusion

Quicksort is a very efficient sorting method that provides O(nlog(n)) performance on average. It is relatively easy to implement and these attributes make it a popular and useful sorting method.

Top comments (2)

Collapse
 
shreya profile image
Shreya Purohit

It was a great read, Bonnie. Thanks for sharing!

Collapse
 
the_greatbonnie profile image
Bonnie

Your are welcome, Shreya.

Hey! Check out this week's Meme Monday post