An algorithm is a finite series of steps that a computer would take to implement a task in an efficient manner.
Sorting algorithms are generally used to rearrange elements of an array to follow a certain order. Popular examples of sorting algorithms include Heapsort, Merge sort and Quicksort.
In this article, you would learn the techniques of sorting using a Quicksort algorithm as well as how to implement one in the JavaScript programming language. You would also learn about the algorithmic complexity of this sorting algorithm.
What is Quicksort
Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array. Every other element of the array is swapped such that elements greater than the pivot elements are on one side and the lesser elements are on the other side of the array and the array ends up being partitioned into sub-arrays. The sub-arrays are then sorted recursively until the array is sorted. This is done in place, so a little additional memory space is required to implement the sorting.
Steps in implementing Quicksort
Just like every other algorithm, the Quicksort algorithm has a few techniques that bound its implementation. Let’s dig into the steps involved to correctly implement a Quicksort algorithm.
Selecting a pivot element
The first step is to pick an element from the array as the pivot element. There are different methods applied to select the pivot element but it is worth mentioning that the method used in sleeting the pivot element might affect the resulting speed of your implementation, you would talk more about this in the complexity analysis section of this article.
The pivot element is selected by either of the following technique:
- The first element of the array
- The last element of the array
- A random element selected from the array
This simply means the pivot element could be any element from the array but it’s a better approach to stick to one method for selecting the for this process.
Compare and swap elements with respect to the pivot element
The selected pivot element is then used as a reference to swapping each element of the array in such a way that all elements of the array that are lesser than the pivot element are placed on the left-hand side and all other items greater than the pivot are placed on the right-hand side. This process generates two partitions, a partition with elements that are greater than the pivot element and the other partition that holds elements lesser than the partition. Finally, the pivot element is placed in between the two partitions generated which can be said to now be in its correct index.
Repeat 🔁
The partitioning process is repeated for every resulting partition of the array until every single item is ultimately in the right place, the array is then said to be fully sorted.
An example of implementing Quicksort
Let’s see a quick example of the process of implementing a Quicksort algorithm by sorting an unordered array. We would look at how to implement this algorithm using a programming language later in this article.
There would have two pointers; the right pointer and the left pointer pointing to both extreme indexes of the array. By comparing the elements at both pointers to that of the pivot element, we decide which element to swap and to which side it should be swiped.
Next, the elements are swapped so that only the items that are lesser than the pivot element are on the left side and the larger elements are swapped to the left. We determine elements to swap by advancing the pointers and comparing each element till we find an element that doesn't match the requirement for the side it resides. The comparison starts from the left pointer, after we have an element that’s lesser than the pivot element, we then find the next element that’s larger than the pivot element from the right pointer to swap out with.
The elements of the unsorted array are listed in the image below:
Images and Indicators
In order to make it easier for you to grasp the concepts, this article provides illustrated images in the examples. The several colours used to indicate the different states and interactions of the elements and the pointers during sorting are described below.
- Gray - Indicates the element’s default state
- Yellow - Indicates a pivot element
- Green - Indicates a sorted element
And the following colours are used for the pointers:
- Green - Indicates the pointer is active
- Pink - Indicates the pointer is inactive
First Iteration
The first step is to select a pivot element. Using the first method for pivot element selection as described above, we select 5 as the pivot element, since it’s the first element of the array.
In this case, the right and left pointers initially point to 5 and 8 respectively. Element 4 is less than the pivot element, we swap it with element 7. The same goes for elements 1 and 6, they are swapped so they are placed on their appropriate sides of the array.
Finally, we move the pivot element 5 to the centre, it is then marked as sorted.
Second Iteration
This first iteration has placed it’s pivot element in its correct position. The iteration also partitioned the array into two sub-arrays each of which also need to be sorted.
We are sorting the left sub-array completely first, then we proceed to the right sub-array. It’s also okay to go the other way round.
Following the same method as in the first iteration, we select the pivot element using the first method so we pick 1.
Scanning through the left pointer, there are no elements greater than the pivot element found so this sub-array is sorted and there would be no swaps on this iteration.
Third Iteration
The second index has placed element 1 in its correct position, we also indicate that with a green background in the image below. It generates another sub-array with two elements.
We select the element on the first index of the third sub-array 2 as the pivot element.
We place the pointers and compare the two elements, all elements of this sub-array also happen to be in place and there are no swaps for this iteration.
We mark the pivot element sorted. Since there is only one item left unmarked from this sub-array, there is no use partitioning it into another subarray since there would be no comparisons or swaps. Instead, the element is also marked as sorted.
Fourth Iteration
The Third iteration has fully sorted every item on the left side. We proceed to the left subarray next.
Select 6 as the pivot element. Comparing the other elements, element 7 is greater than the pivot element 6 so it would not be swapped, the same is true for 9. There would be no swaps in the partition.
We then mark the pivot element for this sub-array 6 as sorted. This is indicated with the green background in the image below.
Fifth Iteration
We’re almost done sorting with just one more partition to go. The last partition contains two elements.
All of the steps are still required, we select the pivot element by picking the first element of the current sub-array 9. 7 is less than 9. We swap both elements places them in order.
We mark the pivot element 9 as sorted, we also mark the last element as sorted since it cannot be broken into a sub-array.
We now have a fully sorted array using the Quicksort algorithm.
Implementing a Quicksort algorithm in javascript
Let’s now take a look at the programmatic method of implementing the Quicksort algorithm in the JavaScript programming language.
open your code editor and create a new file called quicksort.js. This file would hold all the code for the Quicksort algorithm we are implementing.
First, create a function to perform the swap
Code to swap
First paste the code below in your file to create the function swap() :
function swap(unsortedArray, leftIndex, rightIndex){
const temp = unsortedArray[leftIndex];
unsortedArray[leftIndex] = unsortedArray[rightIndex];
unsortedArray[rightIndex] = temp;
}
swap() as its name implies, basically performs a swap of the indexes of the provided elements and replaces the new value into the original array.
Code to perform the partition
Paste the following code for function partition in your quicksort.js file:
const unsortedArray = [];
function partition(unsortedArray, left, right) {
let pivot = unsortedArray[Math.floor((right + left) / 2)], //middle element
i = left, //left pointer
j = right; //right pointer
while (i <= j) {
while (unsortedArray[i] < pivot) {
i++;
}
while (unsortedArray[j] > pivot) {
j--;
}
if (i <= j) {
swap(unsortedArray, i, j); //sawpping two elements
i++;
j--;
}
}
return i;
}
The partition function accepts the unsorted array, starting index and ending index as its arguments. It uses the middle element as the pivot element. The function then swaps the elements of the unsorted array such that all the elements to the left of the pivot are lesser than the pivot and all the elements to the right of the pivot are greater than it. It returns the index of the pivot element in the sorted array after positioning it in its correct position.
unsortedArray would be replaced with the actual values of the array that needs to be sorted.
Implement the sorting
This is the main function that implements quick sort. Update your file to reflect the function:
function quickSort(unsortedArray, left, right) {
let index;
if (unsortedArray.length > 1) {
index = partition(unsortedArray, left, right); //index returned from partition
if (left < index - 1) { //more elements on the left side of the pivot
quickSort(unsortedArray, left, index - 1);
}
if (index < right) { //more elements on the right side of the pivot
quickSort(unsortedArray, index, right);
}
}
return unsortedArray;
}
The quicksort function executes recursively, invoking itself several times until all of the unsorted arrays are completely sorted. It also expects the unsorted array, a starting index and an ending index of the array to be sorted.
It uses the index returned from the function partition to divide the array and perform the Quicksort.
💡 Quicksort is performed on the same array and no new arrays are created in the process.
Time to test your algorithm
unsortedArray currently holds an empty array, update the unsortedArray constant in quicksort.js to now hold the actual values from the example earlier:
const unsortedArray = [5,2,7,6,1,9,4];
Finally, add the code to invoke the function and log the output to the console:
const sortedArray = quickSort(unsortedArray, 0, unsortedArray.length - 1);
console.log(sortedArray);
Now, open up your terminal, locate the file and run the file using node. You can run it by running the command below:
node quicksort.js
Complexity Analysis of Quicksort
The best-case complexity of the quick sort algorithm is O(n logn) also, the average case time complexity is O(*n logn)*.
The worst-case time complexity of Quick Sort is O(n2). The worst-case is usually avoided by using a randomized method for selecting the pivot element.
For the space complexity, Quicksort in-place algorithm, meaning it doesn't take any extra memory space for its implementation because it performs all of the operations on the same array. It takes O(log n) stack space.
Conclusion
This article has walked you through the techniques behind the Quicksort algorithm, an illustrated example as well as how to implement one in javascript.
Thank you for reading and I hope you learned a lot. My name is Azeez Lukman, please stay tuned for more if you would like to keep adding to your algorithmic toolbox 🧰
References
https://www.geeksforgeeks.org/sorting-algorithms/
https://www.interviewbit.com/tutorial/quicksort-algorithm/
Top comments (0)