In this article, we will be discussing the QuickSort algorithm in C, C++ and Java. Quick sort algorithm implementation, detailed working procedure with examples etc will also be discussed here.
Prerequisite: Merge Sort Algorithm
Quicksort is the quickest and one of the most efficient sorting algorithm. Similar to Merge sort, Quick sort follows Divide and conquer algorithm to sort the given array.
The quicksort algorithm is a sorting algorithm that sorts an array by choosing a pivot element, and partition the array around the pivot such that
Elements smaller than the pivot are moved to the left of pivot, and elements larger than the pivot are moved to the right of pivot.
It continues to choose a pivot element and break down the array into single-element array, before combing them back together to form a single sorted array.
Note: Don't get confused as to how to determine a pivot. Simply choose the first/last/ideally the middle element as pivot without any confusion.
Here is how a quick sort algorithm works for a given array of 6 elements.
Here is the step by step implementation of Quick Sort in C, C++ and Java.
Since similar to Merge sort, Quick sort follows divide and conquer algorithm, its complexity in average and best case is same as that of Merge sort which is O(nlogn).
Whereas in the worst case, its complexity is O(n2). This occurs when the given array is nearly or completely sorted.
Important Note: Time complexity of the quick sort algorithm is dependent on the pivot chosen. If the pivot is close to the median or the array, then the number of comparisons required to sort the array are less in number.
After looking at how similar quick sort is to that of Merge sort, you might now be wondering if it is actually better than Merge sort. So here is the answer.
Quicksort is certainly better than Merge sort atleast in case of Arrays.
|Space||Quicksort is an in-place algorithm. Which means that it requires no additional space while sorting the elements.|
Merge sort requires a temporary array to merge the sorted arrays and hence it requires additional space.
|Worst case Complexity||O(n2)|
|Efficiency||Inefficient in case of large arrays and random pivots.|