Example: Quick Sort using Divide and Conquer in C

// Quick Sort using Divide and Conquer
#include <stdio.h>

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

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
   array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
int partition(int arr[], int low, int high) {
    // Step 1: Select the last element as the pivot
    int pivot = arr[high];
    // Index of smaller element and indicates the right position of the pivot found so far
    int i = (low - 1);

    // Step 2: Traverse through all elements and compare each element with pivot
    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++; // Increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    // Step 3: Swap the pivot element with the element at (i + 1)
    swap(&arr[i + 1], &arr[high]);
    // Step 4: Return the partitioning index
    return (i + 1);
}

/* The main function that implements QuickSort
   arr[] --> Array to be sorted,
   low   --> Starting index,
   high  --> Ending index */
void quickSort(int arr[], int low, int high) {
    // Step 1: Base case for recursion - if low is less than high, continue
    if (low < high) {
        // Step 2: Partition the array and get the pivot index
        int pi = partition(arr, low, high);

        // Step 3: Recursively sort elements before partition and after partition
        quickSort(arr, low, pi - 1);  // Sort the left sub-array
        quickSort(arr, pi + 1, high); // Sort the right sub-array
    }
}

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

int main() {
    // Step 1: Initialize an unsorted array
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Apply Quick Sort to the array
    quickSort(arr, 0, n - 1);

    // Step 4: Print the sorted array
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}