Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Quick Sort Algorithm in C, C++ and Java with Examples

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


Quick Sort Algorithm in Brief


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.


Quick Working of Quick Sort Algorithm


Here is how a quick sort algorithm works for a given array of 6 elements.


quick sort algorithm in c


Quick Sort Algorithm in C, C++, Java


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


Time Complexity of Quick Sort


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.


Is Quick Sort better than Merge Sort?


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


Also See Similar DS Sorting Techniques


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