Quick Sort as Divide and Conquer in DSA C++ - Execution Trace

Concept Flow - Quick Sort as Divide and Conquer

Start with full array

↓

Choose pivot element

↓

Partition array around pivot

↓

Left subarray

↓

Recursively apply Quick Sort

↓

Sorted array

Quick Sort picks a pivot, splits the array into smaller parts around it, sorts each part recursively, then combines them.

Execution Sample

DSA C++

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

This code sorts an array by choosing a pivot, partitioning, then sorting left and right parts recursively.

Execution Table

Step	Operation	Pivot	Array State	Partition Indices	Visual State
1	Start quickSort(arr,0,6)	-	[10, 7, 8, 9, 1, 5, 3]	-	[10, 7, 8, 9, 1, 5, 3]
2	Choose pivot arr[6]	3	[10, 7, 8, 9, 1, 5, 3]	i= -1, j=0 to 5	[10, 7, 8, 9, 1, 5, (3)]
3	Compare arr[j]=10 > pivot=3	3	[10, 7, 8, 9, 1, 5, 3]	No swap	[10, 7, 8, 9, 1, 5, (3)]
4	Compare arr[j]=7 > pivot=3	3	[10, 7, 8, 9, 1, 5, 3]	No swap	[10, 7, 8, 9, 1, 5, (3)]
5	Compare arr[j]=8 > pivot=3	3	[10, 7, 8, 9, 1, 5, 3]	No swap	[10, 7, 8, 9, 1, 5, (3)]
6	Compare arr[j]=9 > pivot=3	3	[10, 7, 8, 9, 1, 5, 3]	No swap	[10, 7, 8, 9, 1, 5, (3)]
7	Compare arr[j]=1 <= pivot=3	3	[10, 7, 8, 9, 1, 5, 3]	i=0, swap arr[i] and arr[j]	[1, 7, 8, 9, 10, 5, (3)]
8	Compare arr[j]=5 > pivot=3	3	[1, 7, 8, 9, 10, 5, 3]	No swap	[1, 7, 8, 9, 10, 5, (3)]
9	Place pivot after i=0	3	[1, 7, 8, 9, 10, 5, 3]	Swap arr[i+1] and pivot	[1, 3, 8, 9, 10, 5, 7]
10	Pivot index=1, quickSort left arr[0..0]	-	[1, 3, 8, 9, 10, 5, 7]	-	[1, 3, 8, 9, 10, 5, 7]
11	Left subarray size 1, return	-	[1, 3, 8, 9, 10, 5, 7]	-	[1, 3, 8, 9, 10, 5, 7]
12	quickSort right arr[2..6]	-	[1, 3, 8, 9, 10, 5, 7]	-	[1, 3, 8, 9, 10, 5, 7]
13	Choose pivot arr[6]=7	7	[1, 3, 8, 9, 10, 5, 7]	i=1, j=2 to 5	[1, 3, 8, 9, 10, 5, (7)]
14	Compare arr[j]=8 > pivot=7	7	[1, 3, 8, 9, 10, 5, 7]	No swap	[1, 3, 8, 9, 10, 5, (7)]
15	Compare arr[j]=9 > pivot=7	7	[1, 3, 8, 9, 10, 5, 7]	No swap	[1, 3, 8, 9, 10, 5, (7)]
16	Compare arr[j]=10 > pivot=7	7	[1, 3, 8, 9, 10, 5, 7]	No swap	[1, 3, 8, 9, 10, 5, (7)]
17	Compare arr[j]=5 <= pivot=7	7	[1, 3, 8, 9, 10, 5, 7]	i=2, swap arr[i] and arr[j]	[1, 3, 5, 9, 10, 8, (7)]
18	Place pivot after i=2	7	[1, 3, 5, 9, 10, 8, 7]	Swap arr[i+1] and pivot	[1, 3, 5, 7, 10, 8, 9]
19	Pivot index=3, quickSort left arr[2..2]	-	[1, 3, 5, 7, 10, 8, 9]	-	[1, 3, 5, 7, 10, 8, 9]
20	Left subarray size 1, return	-	[1, 3, 5, 7, 10, 8, 9]	-	[1, 3, 5, 7, 10, 8, 9]
21	quickSort right arr[4..6]	-	[1, 3, 5, 7, 10, 8, 9]	-	[1, 3, 5, 7, 10, 8, 9]
22	Choose pivot arr[6]=9	9	[1, 3, 5, 7, 10, 8, 9]	i=3, j=4 to 5	[1, 3, 5, 7, 10, 8, (9)]
23	Compare arr[j]=10 > pivot=9	9	[1, 3, 5, 7, 10, 8, 9]	No swap	[1, 3, 5, 7, 10, 8, (9)]
24	Compare arr[j]=8 <= pivot=9	9	[1, 3, 5, 7, 10, 8, 9]	i=4, swap arr[i] and arr[j]	[1, 3, 5, 7, 8, 10, (9)]
25	Place pivot after i=4	9	[1, 3, 5, 7, 8, 10, 9]	Swap arr[i+1] and pivot	[1, 3, 5, 7, 8, 9, 10]
26	Pivot index=5, quickSort left arr[4..4]	-	[1, 3, 5, 7, 8, 9, 10]	-	[1, 3, 5, 7, 8, 9, 10]
27	Left subarray size 1, return	-	[1, 3, 5, 7, 8, 9, 10]	-	[1, 3, 5, 7, 8, 9, 10]
28	quickSort right arr[6..6]	-	[1, 3, 5, 7, 8, 9, 10]	-	[1, 3, 5, 7, 8, 9, 10]
29	Right subarray size 1, return	-	[1, 3, 5, 7, 8, 9, 10]	-	[1, 3, 5, 7, 8, 9, 10]
30	All subarrays sorted, done	-	[1, 3, 5, 7, 8, 9, 10]	-	[1, 3, 5, 7, 8, 9, 10]

💡 Recursion ends when subarray size is 1 or 0 (low >= high)

Variable Tracker

Variable	Start	After Step 7	After Step 9	After Step 17	After Step 18	After Step 24	After Step 25	Final
arr	[10,7,8,9,1,5,3]	[1,7,8,9,10,5,3]	[1,3,8,9,10,5,7]	[1,3,5,9,10,8,7]	[1,3,5,7,10,8,9]	[1,3,5,7,8,10,9]	[1,3,5,7,8,9,10]	[1,3,5,7,8,9,10]
pivot	3	3	3	7	7	9	9	-
i	-1	0	0	2	2	4	4	-
pi (pivot index)	-	1	1	3	3	5	5	-

Key Moments - 3 Insights

Why do we swap elements only when arr[j] <= pivot during partition?

Because we want all elements less or equal to pivot on the left side. This is shown in steps 7 and 17 where i moves and swaps happen only when arr[j] <= pivot.

Why does recursion stop when low >= high?

Because subarrays of size 1 or 0 are already sorted. This is shown in steps 11, 20, 27, and 29 where quickSort returns immediately.

Why do we place the pivot after the last smaller element?

To ensure pivot is in its correct sorted position. This happens in steps 9, 18, and 25 where pivot is swapped to i+1 position.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the array state after the swap?

A ]3 ,5 ,01 ,9 ,8 ,7 ,1[

B [10, 7, 8, 9, 1, 5, 3]

C [1, 7, 8, 9, 10, 5, 3]

D 1, 7, 8, 9, 10, 5, 3]

💡 Hint

Check the 'Array State' column at step 7 in the execution_table.

At which step does the pivot first get placed in its correct position?

A Step 18

B Step 9

C Step 25

D Step 7

💡 Hint

Look for 'Place pivot after i=0' operation in execution_table.

If the pivot was chosen as the first element instead of last, how would the partition indices change?

A i would start at low, j would iterate from low+1 to high

B i would start at -1, j would iterate from low to high-1

C i would start at high, j would iterate backwards

D No change in indices

💡 Hint

Partition logic depends on pivot position; see partition indices in steps 2 and 13.

Concept Snapshot

Quick Sort divides array by pivot
Partition places pivot correctly
Recursively sort left and right parts
Stops when subarray size ≤ 1
Efficient average O(n log n) sorting
In-place, no extra arrays needed

Full Transcript

Quick Sort works by picking a pivot element from the array. It then rearranges the array so that all elements less than or equal to the pivot come before it, and all greater elements come after. This is called partitioning. After partitioning, the pivot is in its correct sorted position. Then Quick Sort is called recursively on the left and right subarrays around the pivot. The recursion stops when the subarray has one or zero elements, which are already sorted. This process sorts the entire array efficiently. The execution table shows each step of partitioning and recursive calls, tracking how the array changes and where the pivot is placed. The variable tracker follows the array and pivot index changes. Key moments clarify why swaps happen only for elements less than or equal to the pivot, why recursion stops, and why the pivot is placed after smaller elements. The visual quiz tests understanding of array states and pivot placement during execution.

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