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

Concept Flow - Quick Sort as Divide and Conquer

Choose pivot element

↓

Partition array into two parts

↓

v < pivot

↓

Recursively apply Quick Sort

↓

Combine parts

↓

Sorted array

Quick Sort picks a pivot, splits the array into smaller and bigger parts, sorts each part by repeating the same steps, then combines them.

Execution Sample

DSA C#

int[] arr = {5, 3, 8, 4, 2};
QuickSort(arr, 0, arr.Length - 1);

void QuickSort(int[] a, int low, int high) {
  if (low < high) {
    int p = Partition(a, low, high);
    QuickSort(a, low, p - 1);
    QuickSort(a, p + 1, high);
  }
}

int Partition(int[] a, int low, int high) {
  int pivot = a[high];
  int i = low - 1;
  for (int j = low; j < high; j++) {
    if (a[j] <= pivot) {
      i++;
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
  }
  int temp1 = a[i + 1];
  a[i + 1] = a[high];
  a[high] = temp1;
  return i + 1;
}

This code sorts the array by choosing a pivot and partitioning the array around it recursively.

Execution Table

Step	Operation	Array State	Pivot	Partition Indices	Visual State
1	Start QuickSort(0,4)	[5, 3, 8, 4, 2]	2 (last element)	low=0, high=4	[5, 3, 8, 4, 2]
2	Partition: i=-1, j=0	[5, 3, 8, 4, 2]	2	i=-1, j=0	[5, 3, 8, 4, 2]
3	Compare arr[j]=5 > pivot=2	[5, 3, 8, 4, 2]	2	i=-1, j=0	[5, 3, 8, 4, 2] (no swap)
4	Compare arr[j]=3 > pivot=2	[5, 3, 8, 4, 2]	2	i=-1, j=1	[5, 3, 8, 4, 2] (no swap)
5	Compare arr[j]=8 > pivot=2	[5, 3, 8, 4, 2]	2	i=-1, j=2	[5, 3, 8, 4, 2] (no swap)
6	Compare arr[j]=4 > pivot=2	[5, 3, 8, 4, 2]	2	i=-1, j=3	[5, 3, 8, 4, 2] (no swap)
7	Swap pivot with arr[i+1]	[2, 3, 8, 4, 5]	2	i= -1 + 1 = 0	[2, 3, 8, 4, 5]
8	Pivot index=0, recurse left QuickSort(0,-1)	[2, 3, 8, 4, 5]	-	-	No action (low >= high)
9	Recurse right QuickSort(1,4)	[2, 3, 8, 4, 5]	5 (last element)	low=1, high=4	[2, 3, 8, 4, 5]
10	Partition: i=0, j=1	[2, 3, 8, 4, 5]	5	i=0, j=1	[2, 3, 8, 4, 5]
11	Compare arr[j]=3 <= pivot=5	[2, 3, 8, 4, 5]	5	i=1, j=1	Swap arr[i]=3 with arr[j]=3 (same)
12	Compare arr[j]=8 > pivot=5	[2, 3, 8, 4, 5]	5	i=1, j=2	No swap
13	Compare arr[j]=4 <= pivot=5	[2, 3, 8, 4, 5]	5	i=2, j=3	Swap arr[i]=8 with arr[j]=4 → [2, 3, 4, 8, 5]
14	Swap pivot with arr[i+1]	[2, 3, 4, 5, 8]	5	i=2 + 1 = 3	[2, 3, 4, 5, 8]
15	Pivot index=3, recurse left QuickSort(1,2)	[2, 3, 4, 5, 8]	4 (last element in subarray)	low=1, high=2	[2, 3, 4, 5, 8]
16	Partition: i=0, j=1	[2, 3, 4, 5, 8]	4	i=0, j=1	[2, 3, 4, 5, 8]
17	Compare arr[j]=3 <= pivot=4	[2, 3, 4, 5, 8]	4	i=1, j=1	Swap arr[i]=3 with arr[j]=3 (same)
18	Swap pivot with arr[i+1]	[2, 3, 4, 5, 8]	4	i=1 + 1 = 2	[2, 3, 4, 5, 8]
19	Pivot index=2, recurse left QuickSort(1,1)	[2, 3, 4, 5, 8]	-	-	No action (low >= high)
20	Recurse right QuickSort(3,2)	[2, 3, 4, 5, 8]	-	-	No action (low >= high)
21	Recurse right QuickSort(4,4)	[2, 3, 4, 5, 8]	-	-	No action (low >= high)
22	All recursive calls done	[2, 3, 4, 5, 8]	-	-	Sorted array

💡 All subarrays sorted, recursion ends when low >= high

Variable Tracker

Variable	Start	After Step 7	After Step 14	After Step 18	Final
Array	[5, 3, 8, 4, 2]	[2, 3, 8, 4, 5]	[2, 3, 4, 5, 8]	[2, 3, 4, 5, 8]	[2, 3, 4, 5, 8]
Pivot Index	-	0	3	2	2
i (partition pointer)	-1	0	3	2	2
low	0	0	1	1	1
high	4	4	4	2	2

Key Moments - 3 Insights

Why do we swap the pivot with arr[i+1] at the end of partition?

Because all elements before i+1 are less or equal to pivot, so placing pivot at i+1 keeps smaller elements left and bigger right (see step 7 and 14 in execution_table).

Why does recursion stop when low >= high?

Because a subarray with zero or one element is already sorted, so no further sorting is needed (see steps 8, 19, 20, 21).

Why do we move i only when arr[j] <= pivot during partition?

Because i tracks the boundary of smaller elements; moving i and swapping arr[i] with arr[j] keeps smaller elements grouped (see steps 11 and 13).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the array state after swapping the pivot?

A [5, 3, 8, 4, 2]

B [2, 3, 8, 4, 5]

C [2, 3, 4, 5, 8]

D [3, 2, 8, 4, 5]

💡 Hint

Check the 'Array State' and 'Visual State' columns at step 7 in execution_table.

At which step does the pivot index become 3 during the sorting process?

A Step 14

B Step 7

C Step 18

D Step 10

💡 Hint

Look for 'Pivot index=3' in the 'Operation' column of execution_table.

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

A Partition would start comparing from the end towards the start

B Partition would not change at all

C Partition would compare elements differently and swap pivot at the end

D Partition would skip swapping pivot

💡 Hint

Consider how pivot position affects partition logic and swapping in execution_table.

Concept Snapshot

Quick Sort divides array by pivot
Partition splits smaller and bigger elements
Recursively sort subarrays
Pivot placed correctly after partition
Stops when subarray size ≤ 1
Efficient divide and conquer sorting

Full Transcript

Quick Sort picks a pivot element, usually the last in the current subarray. It partitions the array so that elements less than or equal to the pivot come before it, and greater elements come after. This is done by moving a pointer i to track smaller elements and swapping as needed. After partitioning, the pivot is swapped into its correct position at i+1. Then Quick Sort is called recursively on the left and right subarrays around the pivot. The recursion stops when subarrays have zero or one element, which are already sorted. This divide and conquer approach efficiently sorts the entire array.

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

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 elements by counting their frequency

Solution

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

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

2. Step 2: Compare with other sorting methods

   Unlike bubble sort or counting sort, Quick Sort uses division and conquering subproblems.

3. Final Answer:

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

4. Quick Check:

   Divide and conquer = splitting and sorting parts [OK]

Hint: Remember: Quick Sort splits and sorts parts separately [OK]

Common Mistakes:

• Confusing Quick Sort with bubble sort
• Thinking Quick Sort uses extra memory like merge sort
• Believing Quick Sort counts frequencies

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

easy

A. public static 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, int pivot)

D. public int Partition(int arr, int low, int high)

Solution

1. Step 1: Check C# method declaration syntax

   In C#, arrays are declared as int[] arr, and method must specify return type and access modifier.

2. Step 2: Validate parameters and return type

   Partition returns an integer index, so return type is int. Parameters include array and two indices.

3. Final Answer:

   public static int Partition(int[] arr, int low, int high) -> Option A

4. Quick Check:

   C# method syntax with array and return int = public static int Partition(int[] arr, int low, int high) [OK]

Hint: Remember C# arrays use [] after type, method needs return type [OK]

Common Mistakes:

• Using C-style array syntax like int arr[]
• Missing return type or access modifier
• Passing pivot as parameter unnecessarily

3. What will be the output array after applying Quick Sort on int[] arr = {4, 2, 7, 1}?

medium

A. [1, 2, 4, 7]

B. [7, 4, 2, 1]

C. [2, 1, 4, 7]

D. [4, 7, 2, 1]

Solution

1. Step 1: Apply Quick Sort partition and recursive calls

   Pivot chosen (commonly last element 1), partition places 1 at start, then sort left and right parts recursively.

2. Step 2: Sort remaining parts

   After partitioning and recursive sorting, array becomes sorted ascending: 1, 2, 4, 7.

3. Final Answer:

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

4. Quick Check:

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

Hint: Quick Sort outputs sorted array ascending by default [OK]

Common Mistakes:

• Confusing pivot placement
• Not sorting both sides recursively
• Assuming output is reversed

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. The initial value of i should be low - 1

B. Swap method is called with values, not indices

C. The loop should run until j <= high

D. Pivot should be arr[low], not arr[high]

Solution

1. Step 1: Analyze Swap usage in C#

   Swap is called with arr[i] and arr[j], which passes values, not array indices, so original array won't change.

2. Step 2: Correct Swap call

   Swap should be called with indices or use a method that swaps elements in the array by index.

3. Final Answer:

   Swap method is called with values, not indices -> Option B

4. Quick Check:

   Swap needs indices or ref to swap array elements [OK]

Hint: Swap array elements by indices, not by passing values [OK]

Common Mistakes:

• Using wrong loop range
• Incorrect pivot choice
• Initializing i incorrectly

5. Given an array int[] arr = {3, 6, 8, 10, 1, 2, 1}, how many recursive calls will Quick Sort make to fully sort this array using the last element as pivot each time?

hard

A. 7

B. 15

C. 13

D. 9

Solution

1. Step 1: Understand recursive calls in Quick Sort

   Each partition divides array into two parts; recursive calls happen on both sides unless base case reached.

2. Step 2: Trace recursive calls for given array

   Initial call on 7 elements, partitions and recurses on subarrays. Counting calls: initial + left + right calls totals 9.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Counting recursive calls carefully = 9 [OK]

Hint: Count initial call plus calls on subarrays after partition [OK]

Common Mistakes:

• Counting only partition steps, not recursive calls
• Assuming calls equal array length
• Ignoring base case stops