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 into two parts

↓

Elements < pivot

↓

Recursively quick sort

↓

Combine sorted parts + pivot

↓

Sorted array

Quick Sort splits the array by a pivot, sorts parts separately, 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 dividing it around a pivot and sorting subarrays recursively.

Execution Table

Step	Operation	Array State	Pivot	Partition Action	Resulting Subarrays
1	Start quickSort on full array	[10, 7, 8, 9, 1, 5]	N/A	N/A	Full array: [10,7,8,9,1,5]
2	Choose pivot	[10, 7, 8, 9, 1, 5]	5	Prepare partition around 5	Contains elements <5 (1) and >5
3	Partition step	[1, 7, 8, 9, 10, 5]	5	Swap 10↔1, then 5↔7	Array after partition: [1,5,8,9,10,7]
4	Pivot placed at index 1	[1, 5, 8, 9, 10, 7]	5	Pivot 5 in correct place	Left subarray: [1], Right subarray: [8,9,10,7]
5	Recurse left subarray	[1]	N/A	Single element, no action	Sorted left subarray: [1]
6	Recurse right subarray	[8, 9, 10, 7]	7	Choose pivot 7	Partition around 7
7	Partition step	[1, 5, 7, 9, 10, 8]	7	Swap 8↔7 (pivot to pos 2)	Full array after partition: [1,5,7,9,10,8]
8	Pivot placed at index 2	[1, 5, 7, 9, 10, 8]	7	Pivot 7 in correct place	Left subarray: [], Right subarray: [9,10,8]
9	Recurse left subarray	[]	N/A	Empty subarray, no action	Sorted left subarray: []
10	Recurse right subarray	[9, 10, 8]	8	Choose pivot 8	Partition around 8
11	Partition step	[1, 5, 7, 8, 10, 9]	8	Swap 9↔8 (pivot to pos 3)	Full array after partition: [1,5,7,8,10,9]
12	Pivot placed at index 3	[1, 5, 7, 8, 10, 9]	8	Pivot 8 in correct place	Left subarray: [], Right subarray: [10,9]
13	Recurse left subarray	[]	N/A	Empty subarray, no action	Sorted left subarray: []
14	Recurse right subarray	[10, 9]	9	Choose pivot 9	Partition around 9
15	Partition step & combine	[1, 5, 7, 8, 9, 10]	9	Swap 10↔9 (pivot to pos 4)	Final sorted array: [1,5,7,8,9,10]
16	End	[1, 5, 7, 8, 9, 10]	N/A	Sorting complete	Sorted array returned

💡 Recursion ends when subarrays have zero or one element (base case).

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	Final
arr	[10,7,8,9,1,5]	[1,5,8,9,10,7]	[1,5,8,9,10,7]	[1,5,8,9,10,7]	[1,5,7,9,10,8]	[1,5,7,9,10,8]	[1,5,7,8,10,9]	[1,5,7,8,9,10]
pivot	N/A	5	5	7	7	8	8	N/A
low	0	0	0	2	2	3	3	N/A
high	5	5	5	5	5	5	5	N/A
pi (pivot index)	N/A	1	1	N/A	2	N/A	3	N/A

Key Moments - 3 Insights

Why does the pivot end up in the middle after partition?

Because partition swaps elements so that all smaller are left and larger are right, placing pivot at its correct sorted position (see Step 4 in execution_table).

Why do we stop recursion when subarray has one or zero elements?

Because such subarrays are already sorted, so no further action is needed (see Steps 5, 9, 13).

How does partition rearrange elements around the pivot?

Partition moves elements smaller than pivot to the left and larger to the right by swapping during traversal (see Steps 3, 7, 11, 15).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, where is the pivot placed in the array?

A At index 0

B At index 1

C At index 5

D At index 3

💡 Hint

Check the 'Pivot placed at index 1' row in execution_table.

At which step does the recursion stop for the left subarray containing only one element?

A Step 5

B Step 9

C Step 13

D Step 14

💡 Hint

Look for 'Single element, no action' for left subarray in execution_table.

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

A Partition would not work and sorting would fail

B Pivot would always be placed at the start

C Partition steps would swap different elements but overall logic remains same

D Recursion would stop earlier

💡 Hint

Partition logic depends on pivot position but still rearranges elements around it (see partition steps 3,7,11).

Concept Snapshot

Quick Sort divides array by pivot,
Partitions elements smaller and larger,
Recursively sorts subarrays,
Combines sorted parts,
Stops when subarray size ≤ 1.

Full Transcript

Quick Sort works by choosing a pivot element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then sorted recursively. This divide and conquer approach continues until the subarrays have one or zero elements, which are inherently sorted. The partition step rearranges the array so that the pivot is placed in its correct sorted position, with smaller elements to the left and larger to the right. The process repeats on the left and right subarrays until the entire array is sorted.