C program to implement quick sort algorithm

Quick sort algorithm implementation: In this tutorial, we will learn about the quick sort algorithm, how it works, and implementation of quick sort algorithm using C program. By Sneha Dujaniya Last updated : August 03, 2023

Quick Sort

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 with explanation

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)

C program to implement quick sort algorithm

#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.