 Explore
Placement Prep Edit 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, 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  