Fast Sorting Algorithms Part 2

Here is one of the quickest sorting algorithms even you can know it from its name😅Quick sort Algorithm.

The quick sort algorithm has the same time complexity as the merge sort and in some cases, it might be worse in time complexity than the merge sort.

of course, now you wonder why I even do quick sort if it might be worse than merge sort which is more consistent and has constant time complexity in all cases well It depends on the type of data structure you sorted and how much it’s already sorted.

In terms of how much data is already sorted or nearly sorted The worst case of the quick sort has a time complexity of O(n²) but a merge sort will still have the same time complexity of O(n log₂(n)) so merge sort in this case is better.

In terms of your data structure type If you are sorting an array it will be better to use quick sort as it doesn’t require extra storage as merge sort which has a space complexity of O(n) when it is used to sort an array and that may be quite expensive and it increases the time needed to sort the array so as conclusion quick sort is better in sorting arrays but merge sort is good in sorting linked-lists as it space complexity will be O(1) instead of O(n).

To implement quick sort we need a swap function, pivot function and finally the quick sort algorithm function itself.

let’s start with the swap function which all it does is swap two elements inside the array and it’s used by the pivot function.

The pivot function returns the right spot for the element you pass to it. Choosing the right pivot improves the efficiency of this algorithm if you can detect the median value inside the array then it will be the perfect pivot to start with but in our case, we will consider the pivot as the first element in the array.

The image below contains an example of how the pivot function runs and shows that the main mission of this function is to put a number in its right spot how?

by ensure that every element come before pivot less than pivot and every element come after pivot is bigger than pivot.

The quick sort algorithm is a recursive function which uses a pivot to arrange the left and right sides of it and below is the implementation of it.

How does it work the below image contains an example of how the quick sort function works that makes it clear how things are done behind the scenes.

This was the quick sort algorithm explanation Next we have the parallel sorting algorithms so stay tuned for more exciting topics😉.