Quick Sort Algorithm in DSA C

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

Analogy: Imagine sorting a pile of books by picking one book as a divider, then putting all smaller books on one side and bigger books on the other, then repeating this for each side until everything is in order.

Array: [7, 2, 5, 3, 9]
Pivot chosen: 5
Partition:
[2, 3] -> 5 -> [7, 9]

Dry Run Walkthrough

Input: array: [7, 2, 5, 3, 9]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element 9, partition array around 9

[7, 2, 5, 3, 9↑]

Why: Pivot divides array into smaller and larger elements

Step 2: Partition: all elements less than 9 stay left, 9 placed at correct position

[7, 2, 5, 3] -> 9

Why: 9 is largest, so it stays at the end

Step 3: Recursively quick sort left part [7, 2, 5, 3]

[7, 2, 5, 3]

Why: Sort smaller subarray before combining

Step 4: Choose pivot 3, partition around 3

[7, 2, 5, 3↑]

Why: Pivot divides subarray

Step 5: Partition: elements less than 3 to left, 3 placed correctly

[2] -> 3 -> [5, 7]

Why: 3 placed between smaller and larger elements

Step 6: Recursively quick sort left [2] and right [5, 7]

[2] and [5, 7]

Why: Sort subarrays separately

Step 7: Choose pivot 7 in right subarray, partition around 7

[5, 7↑]

Why: Pivot divides subarray

Step 8: Partition: 5 placed before 7

[5] -> 7

Why: 5 is smaller, placed before 7

Step 9: Combine all sorted parts: [2, 3, 5, 7, 9]

[2, 3, 5, 7, 9]

Why: All parts sorted and combined

Result:

Final sorted array: [2, 3, 5, 7, 9]

Annotated Code

DSA C

#include <stdio.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[high]; // choose pivot as last element
    int i = low - 1; // index of smaller element
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]); // place smaller element to left
        }
    }
    swap(&arr[i + 1], &arr[high]); // place pivot after smaller elements
    return i + 1; // return pivot index
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // partition array
        quickSort(arr, low, pi - 1); // sort left subarray
        quickSort(arr, pi + 1, high); // sort right subarray
    }
}

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

int main() {
    int arr[] = {7, 2, 5, 3, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printArray(arr, n);
    return 0;
}

int pivot = arr[high]; // choose pivot as last element

select pivot to divide array

for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } }

move smaller elements left of pivot

swap(&arr[i + 1], &arr[high]); // place pivot after smaller elements

put pivot in correct sorted position

int pi = partition(arr, low, high); // partition array

partition array and get pivot index

quickSort(arr, low, pi - 1); // sort left subarray

recursively sort left side

quickSort(arr, pi + 1, high); // sort right subarray

recursively sort right side

Output

2 -> 3 -> 5 -> 7 -> 9

Complexity Analysis

Time: O(n log n) average case because the array is divided roughly in half each time and all elements are processed during partitioning

Space: O(log n) due to recursive call stack depth in average case

vs Alternative: Compared to bubble sort's O(n^2), Quick Sort is much faster on average but can degrade to O(n^2) in worst case if pivot choices are poor

Edge Cases

empty array

function returns immediately without changes

DSA C

if (low < high) {

array with one element

function returns immediately as array is already sorted

DSA C

if (low < high) {

array with all elements equal

partition places pivot but no swaps needed, recursion ends quickly

DSA C

if (arr[j] < pivot) {

When to Use This Pattern

When you need to sort an array efficiently and can divide the problem into smaller parts around a pivot, use Quick Sort because it sorts in place and is fast on average.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping pivot to correct position
Fix: Always choose pivot (commonly last element) and swap it to its correct place after partitioning

Mistake: Not updating indices correctly during partition
Fix: Increment i only when a smaller element is found and swap with j to keep smaller elements left

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting subarrays recursively.

Use Quick Sort when you want an efficient, in-place sorting algorithm for average cases.

The key insight is partitioning the array so that elements smaller than pivot go left and larger go right, then sorting each side.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Divide the array into smaller parts using a pivot and sort them recursively

B. Compare every element with every other element and swap if needed

C. Insert elements one by one into a sorted list

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element and divides the array into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting of parts

   It then sorts these parts recursively, combining them to get the sorted array.

3. Final Answer:

   Divide the array into smaller parts using a pivot and sort them recursively -> Option A

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: Quick Sort uses a pivot to split and sort recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges arrays like Merge Sort
• Believing Quick Sort inserts elements one by one

2. Which of the following is the correct way to declare the partition function header in C for Quick Sort?

easy

A. int partition(int arr, int low, int high);

B. int partition(int arr[], int low, int high);

C. void partition(int arr[], int low, int high);

D. int partition(int arr[], int start, int end, int pivot);

Solution

1. Step 1: Check parameter types for partition

   The partition function takes an array and two indices low and high to work on a subarray.

2. Step 2: Confirm return type

   It returns an integer index of the pivot after partitioning.

3. Final Answer:

   int partition(int arr[], int low, int high); -> Option B

4. Quick Check:

   Partition returns pivot index [OK]

Hint: Partition returns pivot index; use array and low, high indices [OK]

Common Mistakes:

• Using void return type for partition
• Passing array as int instead of int[]
• Adding extra parameters like pivot

3. What will be the output array after applying Quick Sort on arr = {3, 6, 8, 10, 1, 2, 1}?

medium

A. [3, 6, 8, 10, 1, 2, 1]

B. [10, 8, 6, 3, 2, 1, 1]

C. [1, 1, 2, 3, 6, 8, 10]

D. [1, 2, 1, 3, 6, 8, 10]

Solution

1. Step 1: Apply Quick Sort logic on the array

   Quick Sort rearranges elements around pivots recursively, sorting the array in ascending order.

2. Step 2: Sort the given array

   Sorting {3,6,8,10,1,2,1} results in {1,1,2,3,6,8,10}.

3. Final Answer:

   [1, 1, 2, 3, 6, 8, 10] -> Option C

4. Quick Check:

   Sorted array ascending = [1,1,2,3,6,8,10] [OK]

Hint: Quick Sort outputs sorted array ascending by default [OK]

Common Mistakes:

• Assuming Quick Sort keeps original order
• Confusing ascending with descending order
• Not sorting duplicates correctly

4. Identify the error in this Quick Sort partition function snippet:

int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low;
  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;
}

medium

A. Variable i should start at low - 1, not low

B. Pivot should be arr[low], not arr[high]

C. Loop should run till j <= high, not j < high

D. Swap function is called with wrong arguments

Solution

1. Step 1: Check initialization of i

   In partition, i should start at low - 1 to correctly track smaller elements.

2. Step 2: Analyze loop and swaps

   Starting i at low causes skipping the first element comparison and wrong swaps.

3. Final Answer:

   Variable i should start at low - 1, not low -> Option A

4. Quick Check:

   i = low - 1 fixes partition indexing [OK]

Hint: Initialize i to low - 1 before partition loop [OK]

Common Mistakes:

• Starting i at low causes incorrect partitioning
• Changing pivot position unnecessarily
• Extending loop beyond high index

5. Given an array with many duplicate elements, which modification to Quick Sort helps improve performance?

hard

A. Use Bubble Sort instead for duplicates

B. Always choose the first element as pivot

C. Skip sorting duplicates by checking equality before partition

D. Use 3-way partitioning to separate less than, equal to, and greater than pivot

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Standard Quick Sort can degrade with many duplicates due to repeated swaps and partitions.

2. Step 2: Apply 3-way partitioning

   3-way partitioning divides array into three parts: less than, equal to, and greater than pivot, reducing unnecessary work.

3. Final Answer:

   Use 3-way partitioning to separate less than, equal to, and greater than pivot -> Option D

4. Quick Check:

   3-way partitioning optimizes duplicates [OK]

Hint: 3-way partitioning handles duplicates efficiently [OK]

Common Mistakes:

• Choosing fixed pivot without randomization
• Skipping duplicates without partitioning
• Switching to slower sorts unnecessarily