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.

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