Sorting has become one of the fundamental techniques to perform operations whether its a database system or an app that wants to store numbers or names alphabetically. Many sorting algorithms came into development over the years, and Quick Sort is one of them. It's known as the one of the fastest sorting algorithm till now.
What is sorting?
Sorting means placing elements of a list in a particular order. The order can be numerical or alphabetic. Sorting technique has various applications such as database sorting, sorting customer entries, sorting data in data visualization, or arranging form data in web apps.
What is Quick Sort?
Quick Sort or Partition Exchange Sort, is an in-place sorting algorithm created by British computer scientist Tony Hoare in 1959 and issued in 1961. It's a commonly used algorithm for sorting and is faster than many other sorting algorithms like merge sort, heap sort, etc.
Algorithm of Quick Sort
Quick sort uses the divide-and-conquer approach for sorting the provided list of elements. The algorithm splits the array into sub-arrays to sort the items.
Here is the algorithm of the Quick Sort:
Qsort(array Arr, begin, end)
{
if (begin< end)
{
par = Qsortpartition(Arr, begin, end)
Qsort(Arr, begin, par - 1)
Qsort(Arr, par + 1, end)
}
}
Partition algorithm
The partition algorithm is for re-arranging the sub-arrays.
Qsortpartition(array Arr, start, end)
{
pivot ? Arr[end]
i ? start-1
for j ? start to end -1 {
do if (Arr[j] < pivot) {
then i ? i + 1
swap Arr[i] with Arr[j]
}}
swap Arr[i+1] with Arr[end]
return i+1
}
Implementation of Quick Sort in JavaScript
The backbone of the Quick Sort program is the partitioning stage. In this code, we'll take the middle element as the pivot.
Code:
<html>
<body>
<script>
var items = [23, 34, 45, 23, 2, 34, 45, 45, 5, 3, 2];
function swap(items, leftIndex, rightIndex){
var temp = items[leftIndex];
items[leftIndex] = items[rightIndex];
items[rightIndex] = temp;
}
function partition(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)], //sets the middle element as the pivot
i = left, //the left pointer
j = right; // the right pointer
while (i <= j) {
while (items[i] < pivot) {
i++;
}
while (items[j] > pivot) {
j--;
}
if (i <= j) {
swap(items, i, j); //swaps two elements
i++;
j--;
}
}
return i;
}
function quickSort(items, left, right) {
var index;
if (items.length > 1) {
index = partition(items, left, right); //returns the index from partition
if (left < index - 1) {
quickSort(items, left, index - 1);
}
if (index < right) {
quickSort(items, index, right);
}
}
return items;
}
var sortedArray = quickSort(items, 0, items.length - 1);
document.write(sortedArray); //will print 2, 2, 3, 5, 23, 23, 34, 34, 45, 45, 45
</script>
</body>
</html>
Output:
How the Quick Sorts works
Here is a quick walkthrough on the various steps and stepwise representation of how quicksort will get executed.
Step 1: Select an element from the array and call it the pivot element.
Step 2: Shuffle them so that the elements lesser than the pivot is on the left side, and the others which are greater than the pivot are on the right side of the pivot. The elements with equal value can be on any of the sides. This process is named partitioning.
Step 3: Repeat this process until the entire array gets sorted
Time and Space Complexity of Quick Sort
Let us now discuss the time and space complexity of Quick Sort. Time complexity defines the amount of time the algorithm will take at its best and most efficient form and worst form. The best time complexity of Quick Sort is O(n*log(n)), the Worst-time complexity is O(n^2), and the average time complexity is O(n*log(n)). The weak spot of the algorithm is choosing the wrong pivot, which will give the worst time complexity.
Choosing the middle element of the array as the pivot will give the best time complexity.
The space complexity of the Quick Sort algorithm is O(n) .
Collusion:
In this article, we learned about the Quick Sort sorting technique, its algorithm, and how to implement it in JavaScript. It's one of the fastest sorting techniques that use the divide and conquer strategy for sorting the elements. Also, we gathered insight on how it uses three step approaches to perform its tasks. We have also encountered the fact and applications where developers can use quick sort.