M. Saqib

Quicksort Implementation in C

Quicksort in C

Quicksort is a widely used sorting algorithm known for its efficiency and simplicity. Developed by Tony Hoare in 1960, this sorting technique follows the “divide and conquer” paradigm which makes it a powerful tool for organizing data in ascending or descending order. Programmers find quicksort to be an excellent introduction to sorting algorithms due to its straightforward implementation and elegant design.

The algorithm operates by selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays, where elements less than the pivot are placed on one side, and elements greater than the pivot on the other. This process is then applied recursively to the sub-arrays until the entire array is sorted. Despite its simplicity, quicksort boasts impressive average-case time complexity. As you delve into quicksort, you’ll gain valuable insights into the divide-and-conquer approach widely employed in various problem-solving scenarios.

Quicksort is a well-known sorting algorithm developed by C.A.R. Hoare: Quicksort. Quicksort is an efficient algorithm based on Divide and Conquer rule and is still a commonly used algorithm for sorting. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays and recursively sorting them.

Computer Journal, Vol. 5, 1, 10-15 (1962)

Table of Contents

What are the Steps to Perform Quick Sort?

  1. Pick an element, called a pivot, from the array.
  2. Partition operation – reorder the array so that elements with values less than the pivot come left, and elements with values greater than the pivot come to the right of the pivot.
  3. Recursively apply the above two steps to the sub-arrays i.e. elements to the left and right of the pivot.

How to Pick Pivot Element?

Pivot is picked up in four possible different ways.

  1. Pick first element as pivot which was used is earliest versions of Quick Sort.
  2. Pick last element as pivot also called Lomuto partition.
  3. Pick a random element as pivot.
  4. Pick median as pivot i.e. choosing the median of the first, middle and last element of the partition for the pivot. This is also called “median-of-three”.

Quicksort Variants

  • Multi-pivot or multiquicksort quicksort – Partition the input variable number of pivots and subarrays.
  • External quicksort – This is a kind of three-way quicksort in which the middle partition (buffer) represents a sorted subarray of elements.
  • Three-way Radix Quicksort – This algorithm is a combination of radix sort and quicksort.
  • Quick Radix Sort – This is again combination of radix sort and quicksort with some minor modifications.
  • Block Quicksort – This algorithm performs partition by dividing the input into constant sized blocks.
  • Partial and Incremental Quicksort – Only sorts limited number of smallest or largest elements i.e. top 10 elements. Look at std::partial_sort for details.

Quicksort Algorithm Complexity

On average it makes O (n log n) (big O notation) comparisons to sort n items, but in the worst cases it is as slow as bubble sort i.e O(n2).

Pseudocode of Lomuto Partition

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

Quicksort Implementation in C by using Different Pivoting Techniques

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
 int t = *a;
 *a = *b;
 *b = t;
}

int partition_pivot_last(int array[], int low, int high) {
 int pivot = array[high];
 int i = (low - 1);

 for (int j = low; j < high; j++) {
  if (array[j] < pivot) {
   swap(&array[++i], &array[j]);
  }
 }

 swap(&array[i + 1], &array[high]);
 return (i + 1);
}

int partition_pivot_first(int array[], int low, int high) {
 int pivot = array[low];
 int i = (low + 1);

 for (int j = low + 1; j <= high; j++) {
  if (array[j] < pivot) {
   if (j != i) {
    swap(&array[i], &array[j]);
   }
   i++;
  }
 }

 swap(&array[i - 1], &array[low]);
 return (i - 1);
}

int partition_pivot_random(int array[], int low, int high) {
 int pivot;
 int n = rand();
 pivot = low + n % (high - low + 1); // Randomizing the pivot
 return partition_pivot_last(array, low, high);
}

int partition_pivot_median(int array[], int low, int high) {
 
 int pivot;
 int mid = (low + high) / 2;
 if (array[mid] < array[low]) 
  swap(&array[mid], &array[low]);
 if (array[high] < array[low])
  swap(&array[high], &array[low]);
 if (array[high] < array[mid])
  swap(&array[high], &array[mid]);
 swap(&array[mid], &array[high-1]);
 
 pivot = array[high-1];

 return partition_pivot_last(array, low, high);
}

void quickSort(int array[], int low, int high) { 
 if (low < high) {
  //int pi = partition_pivot_first(array, low, high);
  //int pi = partition_pivot_last(array, low, high);
  //int pi = partition_pivot_random(array, low, high);
  int pi = partition_pivot_median(array, low, high);

  // Sort the elements on the left of pivot
  quickSort(array, low, pi - 1);

  // Sort the elements on the right of pivot
  quickSort(array, pi + 1, high);
 }
}

int main(void) {
 int array[] = { 1,  3,  2,  4,  6,  8,  7,  9,  5 };
 int size = sizeof(array) / sizeof(array[0]);
 for (int i = 0; i < size; i++)
  printf("|%d", array[i]);
 printf("\n");

 quickSort(array, 0, size - 1);

 printf("\n");
 for (int i = 0; i < size; i++)
  printf("|%d", array[i]);

 getchar();
 return 0;
}

Quicksort Implementation With Highlighted Steps

The following implementation works in Visual Studio only as it uses text highlighting technique which is specific to Microsoft Windows only.

#include <stdio.h>
#include <stdlib.h>

//Visual studio specific to show colors etc.
#include <iostream>
#include <windows.h>


void printArray(int array[], int a, int b, int step, int div)
{
 HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
 if (step == 0)
  printf("\n");
 for (int i = 0; i <= 8; i++) {
  if (a == array[i] || b == array[i]) {
   SetConsoleTextAttribute(hConsole, FOREGROUND_RED);
   printf("%d ", array[i]);
  }
  else {
   SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE);
   printf("%d ", array[i]);
  }

 }
 SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE);
 if (step == 99) {
  printf(" ---> Step %d swap(%d, %d) Run: %d\n", step, a, b, div);
 }
 else {
  printf(" ---> Step %d low:%d, high:%d Run: %d\n", step, a, b, div);
 }
}

void swap(int *a, int *b) {
 int t = *a;
 *a = *b;
 *b = t;
}

int partition_pivot_last(int array[], int low, int high, int div) {
 int pivot = array[high];
 int i = (low - 1);
 int step = 0;

 printArray(array, array[low], array[high], 0, div);
 for (int j = low; j < high; j++) {
  if (array[j] < pivot) {
   swap(&array[++i], &array[j]);
   printArray(array, array[i], array[j], ++step, div);
  }
 }

 swap(&array[i + 1], &array[high]);
 printArray(array, array[i + 1], array[high], 99, div);
 return (i + 1);
}

int partition_pivot_first(int array[], int low, int high, int div) {
 int pivot = array[low];
 int i = (low + 1);
 int step = 0;

 printArray(array, array[low], array[high], 0, div);
 for (int j = low + 1; j <= high; j++) {
  if (array[j] < pivot) {
   if (j != i) {
    swap(&array[i], &array[j]);
    printArray(array, array[i], array[j], ++step, div);
   }
   i++;
  }
 }

 swap(&array[i - 1], &array[low]);
 printArray(array, array[i - 1], array[low], 99, div);
 return (i - 1);
}

int partition_pivot_random(int array[], int low, int high, int div) {
 int pivot;
 int n = rand();
 pivot = low + n % (high - low + 1); // Randomizing the pivot
 printArray(array, array[high], array[pivot], 0, div);
 //swap(&array[high], &array[pivot]);
 return partition_pivot_last(array, low, high, div);
}

int partition_pivot_median(int array[], int low, int high, int div) {

 int pivot;
 int mid = (low + high) / 2;
 if (array[mid] < array[low])
  swap(&array[mid], &array[low]);
 if (array[high] < array[low])
  swap(&array[high], &array[low]);
 if (array[high] < array[mid])
  swap(&array[high], &array[mid]);
 swap(&array[mid], &array[high - 1]);

 pivot = array[high - 1];

 //swap(&array[pivot], &array[low]);

 return partition_pivot_last(array, low, high, div);
}

void quickSort(int array[], int low, int high, int div) {
 if (low < high) {
  //int pi = partition_pivot_first(array, low, high, div);
  //int pi = partition_pivot_last(array, low, high, div);
  //int pi = partition_pivot_random(array, low, high, div);
  int pi = partition_pivot_median(array, low, high, div);
  div++;
  // Sort the elements on the left of pivot
  quickSort(array, low, pi - 1, div);

  // Sort the elements on the right of pivot
  quickSort(array, pi + 1, high, div);
 }
}



int main(void) {
 int array[] = { 1,  3,  2,  4,  6,  8,  7,  9,  5 };
 int size = sizeof(array) / sizeof(array[0]);
 for (int i = 0; i < size; i++)
  printf("|%d", array[i]);
 printf("\n");

 quickSort(array, 0, size - 1, 0);

 printf("\n");
 for (int i = 0; i < size; i++)
  printf("|%d", array[i]);

 getchar();
 return 0;
}

See also: Shell Sort Algorithm, Bubble Sort Implementation, Insertion Sort, Selection Sort

Categories: Blog
Tags: AlgorithmsC ProgrammingSorting
M. Saqib: Saqib is Master-level Senior Software Engineer with over 14 years of experience in designing and developing large-scale software and web applications. He has more than eight years experience of leading software development teams. Saqib provides consultancy to develop software systems and web services for Fortune 500 companies. He has hands-on experience in C/C++ Java, JavaScript, PHP and .NET Technologies. Saqib owns and write contents on mycplus.com since 2004.
Related Post
  1. Differences Between malloc and calloc in C Programming

    In C programming, dynamic memory allocation allows us to allocate memory at runtime. Two commonly used functions for this purpose are malloc and calloc. While…

  2. Control Flow in C Programming – The for and while Loop

    In C programming, controlling the flow of the program is the key to unleashing the true potential of your code. In this article, we will…

  3. Operators in C Programming

    In C Programming, operators are symbols or keywords used to perform operations on values and variables. These are fundamental to performing various operations in C…

  4. Structure in C Programming

    A structure is combination of different data types. Lets take the example of a book, if we cant to declare a book we will be…

  5. Mastering Data Structures: An Essential Skillset for Programming Students

    Data structures are fundamental concepts for any software application and programming in general. It is an incredibly valuable skill set to serve you in your…