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 separately.

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

Pivot chosen (e.g., last element): 2
Split into:
[ ] 2 [ 8, 3, 7, 6 ]

Then sort left and right parts recursively.

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 -> pivot=2, after partition: [2] 3 7 6 8

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

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

2 [3 7 6 8]

Why: Left part is empty, sort right part to continue divide and conquer

Step 3: Choose pivot 8 in right part, partition around 8

2 [3 7 6] [8]

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

Step 4: Recursively quick sort left part [3,7,6]

2 [3 7 6] 8

Why: Sort smaller sub-array before combining

Step 5: Choose pivot 6, partition around 6

2 [3 6] [7] 8

Why: Pivot 6 splits into smaller and greater elements

Step 6: Recursively quick sort left part [3]

2 3 6 7 8

Why: Single element is already sorted

Result:

[2, 3, 6, 7, 8] -- sorted array

Annotated Code

DSA C++

#include <iostream>
#include <vector>

using namespace std;

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

int main() {
    vector<int> arr = {8, 3, 7, 6, 2};
    quickSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

int pivot = arr[high]; // pivot is 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 elements smaller or equal to pivot to left side

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

place pivot after smaller elements and return pivot index

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 processed once per level

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

vs Alternative: Compared to bubble sort's O(n^2), Quick Sort is faster on average due to divide and conquer splitting

Edge Cases

empty array

function returns immediately without changes

DSA C++

if (low < high) {

array with one element

function returns immediately as low is not less than high

DSA C++

if (low < high) {

array with all equal elements

partition keeps elements in place, recursion ends quickly

DSA C++

if (arr[j] <= pivot) {

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently, especially with divide and conquer hints, think of Quick Sort because it splits data around a pivot and sorts parts recursively.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping pivot to correct position
Fix: Always swap pivot to its correct sorted position after partitioning

Mistake: Not updating indices correctly during partition causing infinite loops or wrong partitions
Fix: Use separate pointers for scanning and swapping smaller elements carefully

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting parts 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 as a divide and conquer method?

easy

A. Use extra memory to merge two sorted arrays

B. Sort the array by repeatedly swapping adjacent elements

C. Divide the array into smaller parts, sort them, and combine results

D. Sort the array by selecting the smallest element each time

Solution

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

   Quick Sort divides the array into parts around a pivot, then sorts each part separately.

2. Step 2: Recognize the sorting and combining process

   After dividing, it sorts the parts recursively and combines them by the nature of recursion.

3. Final Answer:

   Divide the array into smaller parts, sort them, and combine results -> Option C

4. Quick Check:

   Divide and conquer = divide, sort, combine [OK]

Hint: Remember: divide, sort parts, then combine [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort uses extra memory like Merge Sort
• Believing Quick Sort selects smallest element each time

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

easy

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

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

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

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

Solution

1. Step 1: Identify correct parameter types

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

2. Step 2: Check return type

   Partition returns an integer index where the pivot finally sits.

3. Final Answer:

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

4. Quick Check:

   Partition returns int index with arr[], low, high [OK]

Hint: Partition returns pivot index, takes array and two indices [OK]

Common Mistakes:

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

3. What will be the output array after one partition call on arr = [4, 7, 2, 9, 1] with low=0 and high=4 if pivot is chosen as last element?

medium

A. [1, 4, 2, 7, 9]

B. [4, 7, 2, 9, 1]

C. [1, 2, 7, 9, 4]

D. [1, 7, 2, 9, 4]

Solution

1. Step 1: Choose pivot and start partitioning

   Pivot is last element: 1. There are no elements less than 1.

2. Step 2: Rearrange array around pivot

   No swaps occur in the loop since all arr[j] > 1 for j = 0 to 3. Then swap arr[0] and arr[4], resulting in [1, 7, 2, 9, 4].

3. Final Answer:

   [1, 7, 2, 9, 4] -> Option D

4. Quick Check:

   Pivot 1 placed at position 0, all to right > 1 [OK]

Hint: Pivot last element, smaller left, larger right [OK]

Common Mistakes:

• Not moving pivot to correct position
• Swapping elements incorrectly
• Assuming pivot stays at end

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) {
      swap(arr[i], arr[j]);
      i++;
    }
  }
  swap(arr[i], arr[high]);
  return i;
}

medium

A. Initialization of i should be low - 1

B. Loop should run until j <= high

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

D. Swap inside if should be swap(arr[j], arr[i])

Solution

1. Step 1: Check initialization of i

   i should start at low - 1 to track last smaller element index before loop.

2. Step 2: Understand loop and swaps

   Loop runs j from low to high-1 correctly; swapping arr[i+1] and arr[high] places pivot correctly.

3. Final Answer:

   Initialization of i should be low - 1 -> Option A

4. Quick Check:

   i = low - 1 needed for correct partition [OK]

Hint: i starts before low to track smaller elements [OK]

Common Mistakes:

• Starting i at low causes wrong swaps
• Loop running to high causes out-of-bound errors
• Changing pivot position unnecessarily

5. Given an array arr = [10, 80, 30, 90, 40, 50, 70], what is the state of the array after the first full Quick Sort partition step choosing the last element as pivot?

hard

A. [10, 30, 40, 50, 70, 80, 90]

B. [10, 30, 40, 50, 70, 90, 80]

C. [10, 80, 30, 90, 40, 50, 70]

D. [10, 30, 40, 50, 80, 90, 70]

Solution

1. Step 1: Identify pivot and partition

   Pivot is last element 70. Partition rearranges elements less than 70 to left.

2. Step 2: Rearrange array after partition

   Elements less than 70: 10, 30, 40, 50. Elements greater: 80, 90. After partition, pivot 70 placed after smaller elements: [10, 30, 40, 50, 70, 80, 90]

3. Final Answer:

   [10, 30, 40, 50, 70, 80, 90] -> Option A

4. Quick Check:

   Pivot 70 placed after smaller elements [OK]

Hint: Pivot last, smaller left, pivot placed next, larger right [OK]

Common Mistakes:

• Sorting entire array in first step
• Swapping pivot with wrong element
• Assuming pivot moves to last position