Quick Sort Algorithm in DSA C# - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array into two parts

↓

Elements < pivot

↓

Recursively quick sort left part

↓

Combine parts

↓

Sorted array

Quick Sort picks a pivot, splits the array into smaller and larger parts, 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 dividing it around a pivot and sorting the parts recursively.

Execution Table

Step	Operation	Array State	Pivot	Partition Indices	Action
1	Choose pivot	[10, 7, 8, 9, 1, 5]	5	low=0, high=5, i=-1, j=0	Start partitioning
2	Compare arr[j]=10 > pivot=5	[10, 7, 8, 9, 1, 5]	5	i=-1, j=0	No swap, j++
3	Compare arr[j]=7 > pivot=5	[10, 7, 8, 9, 1, 5]	5	i=-1, j=1	No swap, j++
4	Compare arr[j]=8 > pivot=5	[10, 7, 8, 9, 1, 5]	5	i=-1, j=2	No swap, j++
5	Compare arr[j]=9 > pivot=5	[10, 7, 8, 9, 1, 5]	5	i=-1, j=3	No swap, j++
6	Compare arr[j]=1 < pivot=5	[10, 7, 8, 9, 1, 5]	5	i=-1, j=4	i=0, swap arr[i]=10 and arr[j]=1 → [1, 7, 8, 9, 10, 5]
7	End partition loop	[1, 7, 8, 9, 10, 5]	5	i=0, j=5	Swap pivot arr[high]=5 with arr[i+1]=7 → [1, 5, 8, 9, 10, 7]
8	Pivot placed at index 1	[1, 5, 8, 9, 10, 7]	5	pivot index=1	Partition done, recursive calls on subarrays
9	Recursive call on left subarray	[1, 5, 8, 9, 10, 7]	-	low=0, high=0	Base case reached, no action
10	Recursive call on right subarray	[1, 5, 8, 9, 10, 7]	-	low=2, high=5	Start partitioning
11	Choose pivot	[1, 5, 8, 9, 10, 7]	7	low=2, high=5, i=1, j=2	Start partitioning
12	Compare arr[j]=8 > pivot=7	[1, 5, 8, 9, 10, 7]	7	i=1, j=2	No swap, j++
13	Compare arr[j]=9 > pivot=7	[1, 5, 8, 9, 10, 7]	7	i=1, j=3	No swap, j++
14	Compare arr[j]=10 > pivot=7	[1, 5, 8, 9, 10, 7]	7	i=1, j=4	No swap, j++
15	End partition loop	[1, 5, 8, 9, 10, 7]	7	i=1, j=5	Swap pivot arr[high]=7 with arr[i+1]=8 → [1, 5, 7, 9, 10, 8]
16	Pivot placed at index 2	[1, 5, 7, 9, 10, 8]	7	pivot index=2	Partition done, recursive calls on subarrays
17	Recursive call on left subarray	[1, 5, 7, 9, 10, 8]	-	low=2, high=1	Base case reached, no action
18	Recursive call on right subarray	[1, 5, 7, 9, 10, 8]	-	low=3, high=5	Start partitioning
19	Choose pivot	[1, 5, 7, 9, 10, 8]	8	low=3, high=5, i=2, j=3	Start partitioning
20	Compare arr[j]=9 > pivot=8	[1, 5, 7, 9, 10, 8]	8	i=2, j=3	No swap, j++
21	Compare arr[j]=10 > pivot=8	[1, 5, 7, 9, 10, 8]	8	i=2, j=4	No swap, j++
22	End partition loop	[1, 5, 7, 9, 10, 8]	8	i=2, j=5	Swap pivot arr[high]=8 with arr[i+1]=9 → [1, 5, 7, 8, 10, 9]
23	Pivot placed at index 3	[1, 5, 7, 8, 10, 9]	8	pivot index=3	Partition done, recursive calls on subarrays
24	Recursive call on left subarray	[1, 5, 7, 8, 10, 9]	-	low=3, high=2	Base case reached, no action
25	Recursive call on right subarray	[1, 5, 7, 8, 10, 9]	-	low=4, high=5	Start partitioning
26	Choose pivot	[1, 5, 7, 8, 10, 9]	9	low=4, high=5, i=3, j=4	Start partitioning
27	Compare arr[j]=10 > pivot=9	[1, 5, 7, 8, 10, 9]	9	i=3, j=4	No swap, j++
28	End partition loop	[1, 5, 7, 8, 10, 9]	9	i=3, j=5	Swap pivot arr[high]=9 with arr[i+1]=10 → [1, 5, 7, 8, 9, 10]
29	Pivot placed at index 4	[1, 5, 7, 8, 9, 10]	9	pivot index=4	Partition done, recursive calls on subarrays
30	Recursive call on left subarray	[1, 5, 7, 8, 9, 10]	-	low=4, high=3	Base case reached, no action
31	Recursive call on right subarray	[1, 5, 7, 8, 9, 10]	-	low=5, high=5	Base case reached, no action
32	All recursive calls done	[1, 5, 7, 8, 9, 10]	-	-	Array fully sorted

💡 All subarrays reduced to base cases (low >= high), recursion ends

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 15	After Step 22	After Step 28	Final
Array	[10, 7, 8, 9, 1, 5]	[1, 7, 8, 9, 10, 5]	[1, 5, 8, 9, 10, 7]	[1, 5, 7, 9, 10, 8]	[1, 5, 7, 8, 10, 9]	[1, 5, 7, 8, 9, 10]	[1, 5, 7, 8, 9, 10]
Pivot Index	-	1	1	2	3	4	4
i (partition index)	-1	0	0	1	2	3	-
j (current index)	0	4	5	5	5	5	-

Key Moments - 3 Insights

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

Because we want all elements smaller than pivot on the left side. This is shown in execution_table rows 6 and 12 where swaps happen only when arr[j] < pivot.

Why does the pivot get swapped with arr[i+1] at the end of partition?

To place the pivot in its correct sorted position, separating smaller and larger elements. See execution_table rows 7, 15, 22, and 28 for these swaps.

When does the recursion stop in Quick Sort?

When the subarray has zero or one element (low >= high), no further sorting needed. This is shown in execution_table rows 9, 17, 24, 30, and 31.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what change happens to the array?

A Swap arr[i] and arr[j] because arr[j] < pivot

B No swap because arr[j] > pivot

C Pivot is moved to the start

D Partition ends

💡 Hint

Check the 'Action' column at step 6 in execution_table

At which step is the pivot 7 placed in its correct position?

A Step 7

B Step 15

C Step 22

D Step 28

💡 Hint

Look for pivot placement actions in execution_table rows with pivot=7

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

A Partition would start comparing from the second element instead of last

B Pivot swaps would happen at the start of the array

C Partition indices i and j would be initialized differently

D No change in partition steps

💡 Hint

Consider how pivot choice affects initial i and j values in partitioning

Concept Snapshot

Quick Sort Algorithm:
- Choose a pivot (usually last element)
- Partition array: smaller left, larger right
- Recursively sort left and right parts
- Base case: subarray size 0 or 1
- Efficient average O(n log n) sorting method

Full Transcript

Quick Sort works by picking a pivot element and rearranging the array so that elements smaller than the pivot come before it and larger elements come after. This partitioning step uses two pointers to swap elements as needed. After placing the pivot in its correct position, Quick Sort recursively sorts the left and right subarrays. The recursion stops when subarrays have zero or one element. The execution table shows each comparison, swap, and recursive call step by step, tracking how the array changes until fully sorted.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Insert elements one by one into a sorted list

B. Compare every element with every other element and swap if needed

C. Divide the array into smaller parts using a pivot and sort them recursively

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's partitioning

   Quick Sort picks a pivot and divides the array into parts smaller and larger than the pivot.

2. Step 2: Apply recursive sorting

   It then sorts these parts recursively to get the full sorted array.

3. Final Answer:

   Divide the array into smaller parts using a pivot and sort them recursively -> Option C

4. Quick Check:

   Quick Sort = Divide and conquer [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
• Ignoring the pivot concept

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

easy

A. public int Partition(int[] arr, int low, int high)

B. public void Partition(int[] arr, int low, int high)

C. public int Partition(int arr[], int low, int high)

D. void Partition(int[] arr, int low, int high)

Solution

1. Step 1: Understand partition function return type

   The partition function returns the pivot index as an integer after rearranging elements.

2. Step 2: Check C# syntax for arrays and access modifiers

   In C#, arrays are declared as int[] arr and public methods specify return type before method name.

3. Final Answer:

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

4. Quick Check:

   Partition returns int index [OK]

Hint: Partition returns pivot index, so return type must be int [OK]

Common Mistakes:

• Using void instead of int as return type
• Incorrect array syntax like int arr[] in C#
• Missing access modifier or wrong order

3. What will be the output array after one partition call on arr = [8, 3, 7, 6, 2] with pivot as last element (2)?

medium

A. [8, 3, 7, 6, 2]

B. [2, 3, 7, 6, 8]

C. [3, 2, 7, 6, 8]

D. [2, 3, 6, 7, 8]

Solution

1. Step 1: Choose pivot and start partitioning

   Pivot is 2 (last element). Elements less than 2 go left, others right.

2. Step 2: Rearrange elements around pivot

   Only 2 is less or equal to pivot, so it swaps with first element 8. Result: [2, 3, 7, 6, 8]

3. Final Answer:

   [2, 3, 7, 6, 8] -> Option B

4. Quick Check:

   Pivot 2 placed at start [OK]

Hint: Pivot last element; smaller elements move left [OK]

Common Mistakes:

• Not swapping pivot correctly
• Assuming full sort after one partition
• Mixing 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, j);
      i++;
    }
  }
  Swap(arr, i, high);
  return i;
}

medium

A. The loop should use <= high instead of < high

B. The comparison should be <= pivot instead of < pivot

C. Swap should be called outside the loop only once

D. The initial value of i should be low - 1

Solution

1. Step 1: Understand partition index initialization

   Variable i tracks the position for swapping smaller elements. It should start at low - 1 to correctly place elements.

2. Step 2: Check loop and swap logic

   Loop runs from low to high-1, swapping when arr[j] < pivot. Starting i at low causes incorrect swaps.

3. Final Answer:

   The initial value of i should be low - 1 -> Option D

4. Quick Check:

   i starts at low-1 for correct partition [OK]

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

Common Mistakes:

• Starting i at low causes wrong swaps
• Changing loop bounds incorrectly
• Using wrong comparison operator

5. Given the array [10, 7, 8, 9, 1, 5], what is the array state after the first full Quick Sort partition step choosing the last element as pivot?

hard

A. [1, 5, 8, 9, 7, 10]

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

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

D. [1, 5, 8, 9, 10, 7]

Solution

1. Step 1: Identify pivot and partition process

   Pivot is 5 (last element). Elements less than 5 move left, others right.

2. Step 2: Rearrange elements around pivot

   Elements less than 5 are 1 only (index 4). Swap it with index 0: [1, 7, 8, 9, 10, 5]. Then swap index 1 (7) with high (5): [1, 5, 8, 9, 7, 10].

3. Final Answer:

   [1, 5, 8, 9, 7, 10] -> Option A

4. Quick Check:

   Pivot 5 placed correctly after smaller elements [OK]

Hint: Pivot last; smaller left, pivot placed next [OK]

Common Mistakes:

• Assuming full sort after one partition
• Swapping elements incorrectly
• Misplacing pivot index