Understanding Quicksort & Partitioning

Quicksort is a divide-and-conquer algorithm. It selects an element as a pivot and partitions the array such that:

1. All elements smaller than the pivot are placed to its left.
2. All elements greater than the pivot are placed to its right.
3. The sub-arrays on the left and right are recursively sorted.

---

C Code Implementation

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>

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

/* Lomuto partition scheme */
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;
}

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);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original Array:\n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted Array (Quicksort):\n");
    printArray(arr, n);

    return 0;
}

Sample Output

text (ISO Standard)
Copy
Original Array:
10 80 30 90 40 50 70 
Sorted Array (Quicksort):
10 30 40 50 70 80 90 

---

Complexity Analysis

• Best & Average Case Time: O(n log n)
• Worst Case Time: O(n²) (Occurs when the smallest/largest element is always chosen as pivot on already sorted arrays).
• Auxiliary Space: O(log n) recursive call stack depth.

---

Related Guides

• Learn recursion stack mechanics in Functions in C Programming.
• Compare with Bubble Sort in C.