Quick Sort in C: Program to Sort Array Using Quick Sort Algorithm

Introduction

In this tutorial, we will learn how to write a C program to sort an array using the quick sort algorithm.

Quick sort is a highly efficient, comparison-based sorting algorithm that follows the divide-and-conquer paradigm. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays—those less than the pivot and those greater than the pivot. The sub-arrays are then recursively sorted.

Quick sort is used in various real-world applications, such as:

• General-purpose Sorting: Default sorting algorithm in C's qsort() and C++'s std::sort
• Large Datasets: Efficiently sorts large arrays with good average-case performance
• In-place Sorting: Requires minimal extra memory
• Embedded Systems: Used when memory is limited

Visual Example

Let's see how quick sort sorts the array [10, 7, 8, 9, 1, 5]:

[10, 7, 8, 9, 1, 5] → Partition around pivot 5
[1, 5, 8, 9, 10, 7] → 5 is in correct position

[1] is already sorted
[8, 9, 10, 7] → Choose pivot 7 → Partition → [7, 9, 10, 8]

[9, 10, 8] → Choose pivot 8 → Partition → [8, 10, 9]
[10, 9] → Choose pivot 9 → Partition → [9, 10]

C Program for Quick Sort

#include <stdio.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function - places pivot in correct position
int partition(int arr[], int low, int high) {
    // Choose the rightmost element as pivot
    int pivot = arr[high];
    int i = (low - 1);  // Index of smaller element
    
    for(int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to pivot
        if(arr[j] <= pivot) {
            i++;  // Increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if(low < high) {
        // pi is partitioning index, arr[pi] is now at correct position
        int pi = partition(arr, low, high);
        
        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int n, i;
    
    // Ask user for number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    // Declare array
    int arr[n];
    
    // Read elements into the array
    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Perform quick sort
    quickSort(arr, 0, n - 1);
    
    // Display sorted array
    printf("\nSorted array in ascending order: ");
    for(i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

Sample Output

Enter the number of elements: 6
Enter 6 elements:
10 7 8 9 1 5

Sorted array in ascending order: 1 5 7 8 9 10

Another Example:

Enter the number of elements: 8
Enter 8 elements:
64 34 25 12 22 11 90 5

Sorted array in ascending order: 5 11 12 22 25 34 64 90

Example with Negative Numbers:

Enter the number of elements: 6
Enter 6 elements:
-5 10 -2 8 0 -10

Sorted array in ascending order: -10 -5 -2 0 8 10

Program Explanation

Let's break down the code step by step:

1. Include Header File: #include <stdio.h> includes the standard input/output library.
2. swap() Function:
   • Swaps two integer values using pointers
   • Used during the partitioning process
3. partition() Function:
   • Selects the last element as the pivot
   • Places all elements smaller than the pivot to the left
   • Places all elements greater than the pivot to the right
   • Returns the final position of the pivot
4. quickSort() Function:
   • Recursively sorts the array
   • Partitions the array and recursively sorts the left and right subarrays
5. main() Function:
   • Gets user input for the array
   • Calls quickSort(arr, 0, n-1) to sort the array
   • Prints the sorted array

Quick Sort Algorithm

Step-by-step algorithm:

1. Start
2. Read the array elements
3. If low < high:
   • Choose a pivot element (typically the last element)
   • Partition the array around the pivot
   • Recursively sort the left subarray: quickSort(arr, low, pi - 1)
   • Recursively sort the right subarray: quickSort(arr, pi + 1, high)
4. Print the sorted array
5. End

Time and Space Complexity

// Change the comparison in the partition function
if(arr[j] >= pivot) {  // Change <= to >= for descending
    i++;
    swap(&arr[i], &arr[j]);
}

Frequently Asked Questions

Previous Topic: -->> Merge Sort in C   ||   Next topic: -->> Heap Sort in C