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

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.

#include<stdio.h>
int partition(int arr[], int low, int high)
{
int temp;
int pivot = arr[high]; // assuming last element of the array as the pivot element
int i = (low - 1); // assuming the index of i pointer as one position less than the first element
for (int j = low; j <= high - 1; j++) // assuming the index of j pointer as the first position
{

// If current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of i pointer and swap the elemets at index i and j
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swapping the pivot (last) element and element at i + 1 index
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

// returning the index of pivot element having lesser elements to the left and greater elements to the right
return (i + 1);
}
void quick_sort(int arr[], int low, int high)
{
if (low < high)
{

// partitioning the single array into two sub-arrays
int pi = partition(arr, low, high);

// sorting the sub-arrays
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}

int main()
{
int n, i;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, n - 1);
print(arr, n);
}
#include<iostream>
using namespace std;
int partition(int arr[], int low, int high)
{
int temp;
int pivot = arr[high]; // assuming last element of the array as the pivot element
int i = (low - 1); // assuming the index of i pointer as one position less than the first element
for (int j = low; j <= high - 1; j++) // assuming the index of j pointer as the first position
{

// If current element is smaller than or equal to pivot

if (arr[j] <= pivot)
{
i++; // increment index of i pointer and swap the elemets at index i and j
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swapping the pivot (last) element and element at i + 1 index
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

// returning the index of pivot element having lesser elements to the left and greater elements to the right
return (i + 1);
}
void quick_sort(int arr[], int low, int high)
{
if (low < high)
{

// partitioning the single array into two sub-arrays
int pi = partition(arr, low, high);

// sorting the sub-arrays
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

int main()
{
int n, i;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
quick_sort(arr, 0, n - 1);
print(arr, n);
}
import java.util.Scanner;
public class Main
{
public static int partition(int arr[], int low, int high)
{
int temp;
int pivot = arr[high]; // assuming last element of the array as the pivot element
int i = (low - 1); // assuming the index of i pointer as one position less than the first element
for (int j = low; j <= high - 1; j++) // assuming the index of j pointer as the first position
{
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of i pointer and swap the elemets at index i and j
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swapping the pivot (last) element and element at i + 1 index
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

// returning the index of pivot element having lesser elements to the left and greater elements to the right
return (i + 1);
}
public static void quick_sort(int arr[], int low, int high)
{
if (low < high)
{

// partitioning the single array into two sub-arrays
int pi = partition(arr, low, high);

// sorting the sub-arrays
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
public static void print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
quick_sort(arr, 0, n - 1);
print(arr, n);
}
}

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.

ParameterQuick SortMerge Sort
SpaceQuicksort 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 ComplexityO(n2)O(n logn)
EfficiencyInefficient in case of large arrays and random pivots.Very efficient