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.
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.
We will now repeat the same process until only a single or empty list of values remains.
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.
Here is how the final results will look like.
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];
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) {
}
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;
}
}
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 = [];
}
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])
}
}
}
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)];
}
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));
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>
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.
Then navigate to the console and you should be able to see that our values are arranged from the smallest to the largest.
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)
It was a great read, Bonnie. Thanks for sharing!
Your are welcome, Shreya.