Divide and Conquer VTU BCSL40A

Quick Sort

Quick Sort is a fast divide-and-conquer sorting algorithm that partitions the array around a pivot, recursively sorting subarrays. This implementation includes empirical time analysis.

Time Complexity

O(n log n) avg, O(n²) worst

Space Complexity

O(log n)

Paradigm

Divide and Conquer

Introduction

Quick Sort is one of the most efficient sorting algorithms in practice, developed by Tony Hoare in 1959. It uses a divide-and-conquer strategy: select a pivot element, partition the array so elements smaller than pivot go left and larger go right, then recursively sort both halves. Despite O(n²) worst case, its average case O(n log n) and excellent cache performance make it faster in practice than Merge Sort.

Problem Statement

Sort an array of n elements using Quick Sort and analyze time complexity empirically by measuring execution time for random arrays of sizes 5000, 10000, 15000, and 20000.

Real World Applications

→ Default sorting in many programming languages (Java Arrays.sort for primitives)
→ Database sorting and indexing
→ Operating system file sorting
→ Network packet sorting
→ In-memory dataset processing

Algorithm Explanation

Quick Sort picks a pivot (first element here), then partitions: scan from left for elements > pivot, from right for elements ≤ pivot, and swap them. When pointers cross, swap pivot into its correct position. Recursively apply to left and right subarrays. The key insight is that after partitioning, the pivot is in its final sorted position.

Step-by-Step Procedure

1 If low >= high, return (base case — subarray has 0 or 1 elements).
2 Call partition(arr, low, high) to find partition index j.
3 Set pivot = arr[low]. i = low, j = high.
4 Move i right while arr[i] ≤ pivot. Move j left while arr[j] > pivot.
5 If i < j, swap arr[i] and arr[j].
6 When i >= j, swap arr[low] with arr[j] (pivot in final position). Return j.
7 Recursively Quicksort(arr, low, j-1) and Quicksort(arr, j+1, high).

Complete C Program

Quick.c

View on GitHub ↗

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

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

int partition(int arr[], int low, int high) {
    int pivot = arr[low], i = low, j = high;
    while(i < j) {
        while(arr[i] <= pivot && i <= high - 1) i++;
        while(arr[j] > pivot && j >= low + 1) j--;
        if(i < j) swap(&arr[i], &arr[j]);
    }
    swap(&arr[low], &arr[j]);
    return j;
}

void Quicksort(int arr[], int low, int high) {
    if(low < high) {
        int partindex = partition(arr, low, high);
        Quicksort(arr, low, partindex - 1);
        Quicksort(arr, partindex + 1, high);
    }
}

void generateRandomArray(int arr[], int n) {
    srand(time(NULL));
    for(int i = 0; i < n; i++) arr[i] = rand();
}

int main() {
    int num_values[] = {5000, 10000, 15000, 20000};
    for(int i = 0; i < 4; i++) {
        int n = num_values[i];
        int *arr = (int *)malloc(n * sizeof(int));
        generateRandomArray(arr, n);
        clock_t start = clock();
        Quicksort(arr, 0, n - 1);
        clock_t end = clock();
        printf("%d\t%f\n", n, (double)(end - start) / CLOCKS_PER_SEC);
        free(arr);
    }
    return 0;
}

Sample Input & Output

Sample Input

(No input — generates random arrays automatically)

Expected Output

5000    0.003200
10000   0.007100
15000   0.011500
20000   0.016300

Dry Run / Trace

Array: [3, 6, 8, 10, 1, 2, 1]. Pivot = 3 (first element).
i starts at index 0, j at index 6.
i moves right past 3 to 6. j moves left from 1 to 2 (≤3). i<j: swap arr[1]=6 and arr[5]=2 → [3,2,8,10,1,6,1].
i moves to 8 (>3). j moves to 1 (≤3). i>j: stop.
Swap arr[0]=3 with arr[j]=arr[1]=2 → [2,3,8,10,1,6,1]. Pivot 3 is at index 1.
Recurse on [2] and [8,10,1,6,1].

Advantages & Disadvantages

✓ Advantages

+ Average case O(n log n) — very fast in practice
+ In-place sorting — O(log n) stack space only
+ Excellent cache performance
+ Widely used as the standard sorting algorithm

✗ Disadvantages

− O(n²) worst case when pivot is always min or max
− Not stable
− Poor performance on already-sorted arrays with first-element pivot
− Recursive — risk of stack overflow for large arrays

Viva Questions & Answers

Q1. What is the worst case of Quick Sort and when does it occur?

O(n²) — occurs when the pivot is always the smallest or largest element (e.g., sorted array with first-element pivot). Results in n partitions of sizes 0 and n-1.

Q2. How can we improve Quick Sort's worst-case performance?

Use random pivot selection or median-of-three pivot strategy to avoid worst-case behavior.

Q3. Is Quick Sort stable?

No, Quick Sort is not stable. Equal elements may be rearranged during partitioning.

Q4. Why is Quick Sort faster than Merge Sort in practice?

Quick Sort has better cache locality (works in-place), smaller constants, and O(log n) stack space vs O(n) for Merge Sort.

Q5. What is the role of the partition function in Quick Sort?

Partition places the pivot in its correct sorted position and ensures all elements to its left are ≤ pivot and all to its right are > pivot.