Quick Sort Algorithm in DSA C++

Mental Model

Quick Sort picks a pivot and arranges elements so smaller ones go left and bigger ones go right, then sorts each side the same way.

Analogy: Imagine sorting books on a shelf by picking one book as a reference, putting all smaller books to the left and bigger books to the right, then repeating this for each side until all books are sorted.

Array before sorting:
[ 8, 3, 7, 6, 2 ]
Pivot chosen -> 2
Partitioning around pivot:
[ 2, 3, 7, 6, 8 ]
Left side ↑
Right side ↑

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

[8, 3, 7, 6, 2] -> pivot=2
Partitioning: elements < 2 to left, others right

Why: Pivot divides array into smaller and larger parts

Step 2: Swap 2 with first element 8 to place pivot correctly

[2, 3, 7, 6, 8]
Pivot 2 is now at correct position index 0

Why: Pivot must be at its final sorted position

Step 3: Recursively quick sort left subarray [] (empty) and right subarray [3,7,6,8]

Left: []
Right: [3,7,6,8]

Why: Sort smaller parts separately

Step 4: Choose pivot 8 in right subarray, partition around 8

[3,7,6,8]
Pivot=8
All elements < 8, so pivot stays at end

Why: Pivot placement divides array further

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

Left: [3,7,6]
Right: []

Why: Continue sorting smaller parts

Step 6: Choose pivot 6 in left subarray, partition around 6

[3,7,6]
Pivot=6
After partition: [3,6,7]

Why: Pivot placed at correct position

Step 7: Recursively quick sort left subarray [3] and right subarray [7]

Left: [3]
Right: [7]

Why: Single elements are sorted

Step 8: All subarrays sorted, combine results

[2,3,6,7,8]

Why: Final sorted array

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Partition function places pivot at correct position
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // choose last element as pivot
    int i = low - 1; // index of smaller element
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++; // move smaller element index forward
            swap(arr[i], arr[j]); // place smaller element left
        }
    }
    swap(arr[i + 1], arr[high]); // place pivot after smaller elements
    return i + 1; // return pivot index
}

// QuickSort recursive function
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 subarray
        quickSort(arr, pi + 1, high); // sort right subarray
    }
}

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];

select pivot as last element

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

move elements smaller than pivot to left side

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

place pivot after smaller elements

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

partition array and get pivot index

quickSort(arr, low, pi - 1);

recursively sort left subarray

quickSort(arr, pi + 1, high);

recursively sort right subarray

Output

2 3 6 7 8 

Complexity Analysis

Time: O(n log n) average case because each partition divides array roughly in half and sorting happens recursively

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

vs Alternative: Compared to Bubble Sort's O(n^2), Quick Sort is much faster on average but worst case is O(n^2) 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 equal elements

partition places pivot but no swaps needed, recursion continues until base cases

DSA C++

if (arr[j] < pivot) {

When to Use This Pattern

When you need to sort an array efficiently and can pick a pivot to divide and conquer, use Quick Sort because it sorts in place and is fast on average.

Common Mistakes

Mistake: Not updating the index of smaller elements correctly in partition
Fix: Increment i only when a smaller element is found and swap it with current element

Mistake: Forgetting to swap pivot to its correct position after partitioning
Fix: Swap pivot with element at i+1 after partition loop

Mistake: Calling quickSort with wrong subarray boundaries causing infinite recursion
Fix: Call quickSort with low to pi-1 and pi+1 to high correctly

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 with average O(n log n) time.

The key insight is partitioning the array so the pivot is in its final place, then sorting left and right parts separately.

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 using pivot [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
• Assuming 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. void partition(int arr[], int low, int high);

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

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

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

Solution

1. Step 1: Check parameter types and order

   The partition function takes an array and two indices: low and high, both integers.

2. Step 2: Check return type

   It returns an integer index where the pivot finally lies.

3. Final Answer:

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

4. Quick Check:

   Correct function signature = int partition(int arr[], int low, int high); [OK]

Hint: Partition returns pivot index; parameters are array and two ints [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Swapping low and high parameters

3. What will be the output array after applying Quick Sort on arr = {4, 2, 7, 1} using the last element as pivot?

medium

A. [1, 2, 4, 7]

B. [1, 4, 2, 7]

C. [2, 1, 4, 7]

D. [7, 4, 2, 1]

Solution

1. Step 1: Partition with pivot 1

   Pivot is 1 (last element). After partition, array becomes [1, 2, 7, 4] with pivot at index 0.

2. Step 2: Recursively sort subarrays

   Left subarray is empty; right subarray [2,7,4] is sorted recursively to [2,4,7]. Final array is [1,2,4,7].

3. Final Answer:

   [1, 2, 4, 7] -> Option A

4. Quick Check:

   Sorted array = [1, 2, 4, 7] [OK]

Hint: Pivot last element; sort left and right recursively [OK]

Common Mistakes:

• Not placing pivot correctly after partition
• Sorting only once without recursion
• Confusing pivot with first element

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. Swap should be done only if arr[j] <= pivot

B. Loop should run from j = low to j <= high

C. Initialization of i should be low - 1

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

Solution

1. Step 1: Check initialization of i

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

2. Step 2: Analyze loop and swaps

   Loop runs j from low to high-1 correctly; swap with arr[i+1] after loop is correct.

3. Final Answer:

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

4. Quick Check:

   i starts at low - 1 in partition [OK]

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

Common Mistakes:

• Starting i at low causes wrong partitioning
• Loop running to high causes out-of-bound swap
• Changing pivot position incorrectly

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

hard

A. Always choose the first element as pivot

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

C. Skip sorting subarrays with size less than 5

D. Use Bubble Sort instead for duplicates

Solution

1. Step 1: Understand problem with duplicates

   Standard Quick Sort performs poorly with many duplicates due to repeated swaps.

2. Step 2: Apply three-way partitioning

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

3. Final Answer:

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

4. Quick Check:

   Three-way partitioning improves duplicates handling [OK]

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

Common Mistakes:

• Choosing fixed pivot without considering duplicates
• Ignoring small subarrays optimization
• Switching to slower sorts unnecessarily