Link copied to clipboard. Share away!

Dismiss

Published on 12 Mar 2020

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.

C

C++

Java

Output

Input-
12 3 1 6 23 7
Output-
1 3 6 7 12 23

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(n^{2}). 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.

Parameter | Quick Sort | Merge Sort |
---|---|---|

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) | O(n logn) |

Efficiency | Inefficient in case of large arrays and random pivots. | Very efficient |

Check out more Data Structure Questions

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×