Program 11 : Quick Sort

Sort a given set of elements using Quick sort and determine the time required to sort n elements. Repeat the experiment for different values of n and plot a graph of the time taken versus n.

Quick Sort

Hoare partition scheme

#include <stdio.h>

// Hoare partition scheme with inline swap
int partition(int arr[], int low, int high) {
    int pivot = arr[low];  // choose first element as pivot
    int i = low - 1;
    int j = high + 1;

    while (1) {
        // move i to the right
        do {
            i++;
        } while (arr[i] < pivot);

        // move j to the left
        do {
            j--;
        } while (arr[j] > pivot);

        // if indices cross, return j
        if (i >= j)
            return j;

        // swap arr[i] and arr[j] (inline swap)
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

// QuickSort function using Hoare partition
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int partIndex = partition(arr, low, high);
        quickSort(arr, low, partIndex);
        quickSort(arr, partIndex + 1, high);
    }
}

// Display array
void displayArray(int arr[], int n) {
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main
int main() {
    int arr[100], n;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    quickSort(arr, 0, n - 1);
    displayArray(arr, n);

    return 0;
}

Lomuto partition scheme

#include <stdio.h>

// Partition function
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // choose last element as pivot
    int i = low - 1;        // index of smaller element
    int temp;
// i can be -1 but it is never accessed without incrementing
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) 
        {
            i++;
            // swap arr[i] and arr[j]
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1; // pivot index
}

// Recursive quicksort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // partition the array
        int pi = partition(arr, low, high);

        // recursively sort the two halves
        // Partitioned element is in right place 
        // so no need to add it or change it 
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

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

int main() {
    int arr[100], n;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    quickSort(arr, 0, n - 1);
    displayArray(arr, n);

    return 0;
}

---

Explanation of Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting a pivot element, then partitioning the array so that:

• All elements less than the pivot go to its left

• All elements greater than the pivot go to its right

Then it recursively applies the same logic to the left and right subarrays.

---

Example:

Input: {10, 7, 8, 9, 1, 5}

1. Choose pivot: 5

2. Partition array around 5 → {1, [pivot=5], 10, 7, 8, 9}

3. Recur on {1} and {10, 7, 8, 9}

4. Continue until all subarrays are sorted

---

Time Complexity

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n²) (if poorly chosen pivot)

• Space Complexity: O(log n) due to recursion

• In-place: Yes

• Stable: No (can be made stable with extra space)