Home » C/C++ Data Structure programs

# C program to implement Quick Sort Algorithm

**Quick Sort Algorithm**: Here, we are going to learn about the quick sort algorithm, how it works, and C language implementation of the quick sort.

Submitted by Sneha Dujaniya, on June 19, 2020

**Quick Sort** is an algorithm based on the divide and conquers paradigm wherein the problem is solved by dividing it into subproblems and then combining the results of each subproblem. Unlike Merge Sort, where the array is divided using the middle element only, here the array divided using a pivot element. This pivot element may be an element of the array-like first, last, middle, or random.

The default implementation of **Quick Sort** is unstable and in-place.

**Quick Sort** calls two functions in its implementation. One is the *QuickSort()* wherein it recursively calls itself for division purpose and the other is *Partition()* which is used to determine the pivot element around which the division of array takes place. This pivot element is placed at its correct position in the sorted array where the elements at its left are smaller than it and elements at its right are higher than it. The two sub-lists go through the same process again.

**Pseudo code for QuickSort() and Partition():**

Quick_Sort(arr[], low, high) { If high > low: q = partition(arr, low, high) // index of pivot element Quick_Sort(arr, low, q - 1) Quick_Sort(arr, q + 1, high) end if } Partition(arr[], low, high) { pivot = arr[high] //considering last element as pivot i = low – 1 for j -> low to high-1: if arr[j] < pivot: i++ swap arr[i] and arr[j] end if end for swap arr[i + 1] and arr[high] return (i+1) }

**Example:**

**Input Array: **10, 80, 30, 90, 40, 70

**1 ^{st} call for partition:**

Low = 0, high = 5, pivot = arr [high] = 70, i = -1

Traverse j from low to high – 1:

For j = 0,

- arr[j] < pivot, therefore, i++ and swap(arr[i], arr[j])
- Now,
**i = 0** - Arr[] =
**10**80 30 90 40 70

For j = 1,

- Arr[j] > pivot, move forward

For j = 2,

- Arr[j] < pivot, therefor i++ and swap (arr[i], arr[j])
- Now, i = 1
- Arr[] = 10
**30**80 90 40 70

For j = 3,

- Arr[j] > pivot, move forward

For j = 4,

- Arr[j] < pivot, therefor i++ and swap (arr[i], arr[j])
- Now, i = 2
- Arr[] = 10 30
**40**90 80 70

After coming out of for loop:

- Swap arr[i+1] and arr[high]
- Arr[] = 10 30 40
**70**80 90 - Return i + 1, therefore, return index of 70 which is i = 3 as 70 is the pivot element.

Similarly, the two sub lists before 70 and after 70 will be passed for sorting.

We can see that all the elements to the left of 70 are smaller than 70 and all to the right are greater than it. In our example, the two sub lists are already sorted, but when we run the algorithm, the two sub lists would be passed for sorting until each sub list contains exactly one element and hence, is sorted.

**Time Complexity:**

The time complexity of the **Quick Sort** algorithm can be defined by the following recurrence relation for the best and average case only and can be solved by Master’s method:

- T (n) = T (n/2) + Ɵ(n)
- Worst Case = O(N^2)

When the pivot is the smallest or the largest element. When the list is already sorted in either ascending or descending order and we choose the last element as pivot, the worst case will occur. The sublist will consist of n-1 elements after **Partition( )** as the chosen pivot was already at its correct position. As a result, the recurrence relation changes to –

- T (n) = T (n-1) + Ɵ(n)
- Average Case = Ɵ(N log N)
- Best Case = Ω(N log N), when the partition takes place at the middle element always
- Space Complexity: Ɵ(N)

**Quick Sort Implementation:**

#include <stdio.h> void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quick_sort(int arr[], int low, int high) { if (low < high) { int q = partition(arr, low, high); quick_sort(arr, low, q - 1); quick_sort(arr, q + 1, high); } } int main() { int arr[] = { 10, 80, 30, 90, 40, 50, 70 }; int n = sizeof(arr) / sizeof(arr[0]); printf("After performing quick sort:\n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } quick_sort(arr, 0, n - 1); printf("\nAfter performing quick sort:\n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }

**Output:**

After performing quick sort: 10 80 30 90 40 50 70 After performing quick sort: 10 30 40 50 70 80 90

Although the worst case of **quick sort** is **O (N^2)**, it can be optimized with the choice of the pivot element so that the worst-case never occurs. There can be many variants of quick sort.

It is a cache-friendly algorithm and is tail-recursive.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.