Quick Sort Algorithm
Sorting an array of random numbers belonging to a random range is an easy task since the 20ᵗʰ century.
The choice of the algorithm revolves around time and space complexity and various other requirements.
Merge Sort
Merge Sort is a sorting algorithm based on the divide and conquer technique.
In a nutshell, we divide the array into two halves and sort them while merging them back. For an array of N elements, the worst-case time complexity of the merge sort algorithm is O(N*log ₂ N), and the additional space required is O(N).
Quick Sort
Like Merge Sort, the QuickSort algorithm is also based on the divide and conquer technique.
The QuickSort algorithm involves choosing a pivot element. Each iteration is put to its correct position in the array by placing all elements smaller than the pivot element left to pivot element and all the elements greater than the pivot element to the pivot element's right.
Let us dive into the concept of Quick Sort:
Step 1: Choosing a pivot.
In most cases, the last element is chosen as the pivot element for the ease of coding, but it is not necessary to select a specific element as the pivot. In fact, it is possible to attain a higher efficiency by random pivoting.
Step 2: Partitioning
After choosing the pivot element, we put all the numbers smaller to it towards the respective left of the pivot and the greater ones towards the respective right. In this step, the pivot element reaches its correct logical position.
Step 3: Recursion
Recurse the steps for the left and right partition individually. Since Quick Sort is a recursive sorting algorithm, we repeat the above steps for each partition until there is one element left in the partition.
Let us Code Up this Algorithm.
Basic Logic
Partition Logic
Merge Sort vs Quick Sort
Space Complexity Analysis:
Merge requires creating two arrays for the left subpart and the right subpart during the merge step; that sums up to O(N) space requirement.
Quick Sort requires no extra space at any point in the algorithm as it uses in-place partitioning; that sums up to O(1) space requirement.
Time Complexity Analysis:
The worst-case/average time complexity of the Merge Sort algorithm is O(N*log ₂ N).
Whereas the worst-case time complexity of the QuickSort algorithm is O(N²), and the average time complexity is θ(N*log ₂ N).
Why would one choose to use the QuickSort algorithm instead of Merge Sort, taking the basic comparison as time complexity?
Here is why Quick Sort is given preference over Merge Sort:
The runtime of an algorithm often relates to the number of comparisons and swaps involved. Comparing the Quick Sort implementation with Merge Sort, the difference is clearly distinct; Quick Sort involves very few operations than Merge Sort.
Also, Quick Sort exhibits excellent cache locality.
Therefore, a majority of languages implement Quick Sort as their in-built sorting algorithms instead of merge sort.
I hope you find this article helpful. If I missed anything, do let me know.
