Quick Sort as Divide and Conquer in DSA C

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, and then combines them to get a sorted list.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then sorting each side the same way until all cards are in order.

Array before sorting:
[ 8, 3, 7, 6, 2 ]

Pivot chosen (e.g., last element): 2
Partition step divides array into:
[ 2 ] [ 3, 7, 6, 8 ]

Then recursively sort each part.

Dry Run Walkthrough

Input: array: [8, 3, 7, 6, 2]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element (2), partition array around pivot

[2] [3, 7, 6, 8]

Why: Pivot divides array into elements less or equal and greater than pivot

Step 2: Recursively quick sort left part [2] (single element)

[2]

Why: Single element is already sorted

Step 3: Recursively quick sort right part [3, 7, 6, 8], choose pivot 8

[3, 7, 6] [8]

Why: Pivot 8 partitions right part into smaller and equal elements

Step 4: Recursively quick sort [3, 7, 6], choose pivot 6

[3, 6] [7]

Why: Pivot 6 partitions into smaller and greater elements

Step 5: Recursively quick sort [3, 6], choose pivot 6

[3] [6]

Why: Pivot 6 partitions into smaller and equal elements

Step 6: Recursively quick sort [3] (single element)

[3]

Why: Single element is sorted

Step 7: Combine all sorted parts to get final sorted array

[2, 3, 6, 7, 8]

Why: All parts sorted and combined form the fully sorted array

Result:

[2, 3, 6, 7, 8]

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]); // move smaller element to left
        }
    }
    swap(&arr[i + 1], &arr[high]); // place pivot in correct position
    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 part
        quickSort(arr, pi + 1, high); // sort right part
    }
}

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[] = {8, 3, 7, 6, 2};
    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

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

move elements smaller or equal to pivot to left side

swap(&arr[i + 1], &arr[high]); return i + 1;

place pivot in correct sorted position

if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }

recursively sort left and right parts around pivot

Output

2, 3, 6, 7, 8

Complexity Analysis

Time: O(n log n) average case because the array is divided roughly in half each time and each element is compared once per level

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

vs Alternative: Better than simple sorting like bubble sort O(n^2) because it divides problem into smaller parts instead of comparing all pairs

Edge Cases

empty array

function returns immediately without changes

DSA C

if (low < high) {

array with one element

already sorted, no recursive calls happen

DSA C

if (low < high) {

array with all equal elements

partition keeps elements in place, recursion still works correctly

DSA C

if (arr[j] <= pivot) {

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently by splitting into smaller parts, reach for Quick Sort because it uses divide and conquer to sort fast.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping elements properly during partition
Fix: Always pick pivot as last element and swap elements smaller than pivot to left side, then place pivot correctly

Mistake: Not handling base case when low >= high causing infinite recursion
Fix: Add condition if (low < high) before recursive calls

Summary

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

Use Quick Sort when you want an efficient average-case sorting algorithm with divide and conquer.

The key insight is choosing a pivot to split the array and sorting smaller parts independently.

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

easy

A. Compare each element with every other element to sort

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

C. Merge two sorted arrays into one sorted array

D. Insert elements one by one into the correct position

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort picks a pivot 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 results to get a sorted array.

3. Final Answer:

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

4. Quick Check:

   Quick Sort = Divide and conquer with pivot [OK]

Hint: Remember pivot splits array for recursive sorting [OK]

Common Mistakes:

• Confusing Quick Sort with Merge Sort
• Thinking Quick Sort compares all pairs
• 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. void partition(int arr[], int low, int high);

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

D. int partition(int arr[], int low);

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: Check return type

   It returns an integer index where the pivot ends after partitioning.

3. Final Answer:

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

4. Quick Check:

   Partition returns pivot index with array and bounds [OK]

Hint: Partition returns pivot index, needs array and bounds [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Missing one of the index parameters

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

medium

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

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

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

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

Solution

1. Step 1: Apply Quick Sort to the array

   Quick Sort rearranges elements so smaller come before pivot and larger after, recursively sorting subarrays.

2. Step 2: Sort the given array

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

3. Final Answer:

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

4. Quick Check:

   Sorted array = ascending order [OK]

Hint: Quick Sort outputs sorted array ascending [OK]

Common Mistakes:

• Assuming original array stays same
• Confusing ascending with descending order
• Misplacing duplicate elements

4. Identify the error in this Quick Sort partition code 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. For loop should run until j <= high

B. Pivot should be arr[low] instead of arr[high]

C. Swap should be called outside the loop only

D. Variable i should start at low - 1

Solution

1. Step 1: Check initialization of i

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

2. Step 2: Analyze loop and swaps

   Starting i at low causes incorrect swaps and wrong pivot placement.

3. Final Answer:

   Variable i should start at low - 1 -> Option D

4. Quick Check:

   i = low - 1 fixes partition indexing [OK]

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

Common Mistakes:

• Starting i at low causes off-by-one errors
• Changing pivot position incorrectly
• Loop running beyond high index

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

hard

A. Avoid recursion and use iterative sorting only

B. Always pick the first element as pivot

C. Use a three-way partitioning to separate less, equal, and greater elements

D. Skip sorting duplicates to save time

Solution

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

   Duplicates cause many equal elements to be repeatedly partitioned, slowing sorting.

2. Step 2: Apply three-way partitioning

   Three-way partitioning divides array into less than, equal to, and greater than pivot, reducing redundant work.

3. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option C

4. Quick Check:

   Three-way partitioning optimizes duplicates [OK]

Hint: Three-way partition handles duplicates efficiently [OK]

Common Mistakes:

• Picking fixed pivot causes worst-case time
• Skipping duplicates breaks sorting correctness
• Avoiding recursion does not fix duplicate issue