Implementation of Quick Sort Algorithm in C

Quick Sort is a highly efficient sorting algorithm known for its “divide and conquer” strategy. It breaks down the task of sorting into smaller, more manageable pieces. In this article, we’ll walk through how to implement the Quick Sort algorithm using the C programming language. We’ll start with a basic implementation and then explore variations like sorting in reverse order and sorting arrays of custom structures.

Prerequisites:

Core Idea Recap

Before we look at the C code, let’s quickly refresh the main steps involved in Quick Sort:

  1. Choose a Pivot: Select an element from the array to act as a reference point.
  2. Partition: Rearrange the array so that elements smaller than the pivot are to its left, and elements larger are to its right. The pivot ends up in its final sorted position.
  3. Recurse: Apply the Quick Sort algorithm recursively to the sub-arrays on the left and right of the pivot’s final position.
  4. Base Case: The recursion stops when a sub-array has zero or one element (it’s already sorted).

Basic Quick Sort Implementation (Recursive)

Let’s implement Quick Sort in C using recursion. We’ll need functions for partitioning (partition) and the main recursive sorting logic (quickSort). We also need a helper function to swap elements. For simplicity, we’ll use the last element as the pivot in our partition function.

The swap Helper Function

This simple function swaps the values of two integer variables. In C, we pass pointers to the variables to modify them directly.

// Helper function to swap two integer values
void swap(int* a, int* b) {
  int temp = *a; // Store the value pointed to by 'a' in temp
  *a = *b;     // Store the value pointed to by 'b' into the location pointed to by 'a'
  *b = temp;   // Store the value originally from 'a' (now in temp) into the location pointed to by 'b'
}

The partition Function

This function takes the array, the low index (start), and the high index (end) as input. It rearranges the elements within this range around the pivot (the element at arr[high]) and returns the pivot’s final index.

// Function to partition the array and return the pivot index
// It places the pivot element (arr[high]) at its correct sorted position
// and moves all smaller elements to its left and larger elements to its right.
int partition(int arr[], int low, int high) {
  // Choose the last element as the pivot
  int pivot = arr[high];
  
  // i stores the index of the last element that was smaller than or equal to the pivot
  // Initialize i to be one position before the start of the sub-array
  int i = low - 1; 

  // Iterate through the sub-array from low up to (but not including) high
  for (int j = low; j < high; j++) {
    // If the current element is less than or equal to the pivot
    if (arr[j] <= pivot) {
      // Increment i (move the boundary for smaller elements)
      i++;
      // Swap the element at index i with the current element at index j
      // This moves the smaller element arr[j] to the "smaller" side
      swap(&arr[i], &arr[j]);
    }
  }

  // After the loop, the correct position for the pivot is i + 1
  // Swap the pivot (which is at arr[high]) with the element at arr[i + 1]
  swap(&arr[i + 1], &arr[high]);
  
  // Return the index where the pivot is now located
  return i + 1;
}

Explanation:

  • pivot = arr[high]: Selects the last element as the pivot.
  • i = low - 1: i tracks the boundary. Everything at or before index i is less than or equal to the pivot.
  • The for loop iterates through elements from low to high - 1.
  • if (arr[j] <= pivot): If an element is smaller/equal to the pivot, i is incremented, and arr[i] is swapped with arr[j] using our swap function (passing addresses with &).
  • swap(&arr[i + 1], &arr[high]): Finally, the pivot is swapped into its correct position i + 1.
  • The function returns the pivot’s final index.

The quickSort Function

This function implements the main recursive logic. It calls partition and then recursively calls itself on the two resulting sub-arrays.

// The main Quick Sort function
void quickSort(int arr[], int low, int high) {
  // Base case: If low is less than high, there are at least two elements
  // If low >= high, the sub-array has 0 or 1 element, which is already sorted
  if (low < high) {
    // Partition the array and get the pivot's final index (pi)
    int pi = partition(arr, low, high);

    // Recursively call quickSort on the sub-array before the pivot
    // Sort elements from low up to pi - 1
    quickSort(arr, low, pi - 1);

    // Recursively call quickSort on the sub-array after the pivot
    // Sort elements from pi + 1 up to high
    quickSort(arr, pi + 1, high);
  }
}

Explanation:

  • if (low < high): This is the base case check. If the condition is false, the recursion stops for this branch.
  • pi = partition(arr, low, high): Calls the partition function.
  • quickSort(arr, low, pi - 1): Recursive call for the left sub-array.
  • quickSort(arr, pi + 1, high): Recursive call for the right sub-array.

Putting It Together

Here’s a complete C program demonstrating the basic Quick Sort:

#include <stdio.h>

// Helper function to swap two integers
void swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// Partition function (as defined above)
int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low - 1; 
  for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return i + 1;
}

// Quick Sort function (as defined above)
void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

// Utility function to print the array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main() {
  // Example array to sort
  int arr[] = {10, 7, 8, 9, 1, 5};
  int n = sizeof(arr) / sizeof(arr[0]); // Calculate array size

  printf("Original array: ");
  printArray(arr, n);

  // Call quickSort on the entire array
  // low = 0 (start index), high = n-1 (end index)
  quickSort(arr, 0, n - 1);

  printf("Sorted array: ");
  printArray(arr, n);

  return 0;
}

Output:

Original array: 10 7 8 9 1 5 
Sorted array: 1 5 7 8 9 10

Sorting in Descending Order

To sort the array from largest to smallest, modify the comparison in the partition function from <= to >=.

// Partition function modified for descending order
int partition_desc(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low - 1;
  for (int j = low; j < high; j++) {
    // Change comparison to >= for descending sort
    if (arr[j] >= pivot) { 
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return i + 1;
}

// Quick Sort function modified to use the descending partition
void quickSort_desc(int arr[], int low, int high) {
  if (low < high) {
    // Use the descending partition function
    int pi = partition_desc(arr, low, high); 
    quickSort_desc(arr, low, pi - 1);
    quickSort_desc(arr, pi + 1, high);
  }
}

// --- In main() ---
// int arr_desc[] = {10, 7, 8, 9, 1, 5};
// int n_desc = sizeof(arr_desc) / sizeof(arr_desc[0]);
// printf("\nOriginal array for descending sort: ");
// printArray(arr_desc, n_desc);
// quickSort_desc(arr_desc, 0, n_desc - 1);
// printf("Sorted array (descending): ");
// printArray(arr_desc, n_desc);

Output (for descending sort):

Original array for descending sort: 10 7 8 9 1 5 
Sorted array (descending): 10 9 8 7 5 1

What’s Next?

Now that you’ve learned how to implement Quick Sort in C, you can explore further: