Quick Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array around pivot

↓

Left sub-array < pivot

↓

Recursively quicksort left

↓

Combine sorted parts

↓

Sorted array

Quick Sort picks a pivot, splits the array into smaller and bigger 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	Partitioning Action	Resulting Array State
1	Choose pivot	[10, 7, 8, 9, 1, 5]	5	Start partitioning from low=0 to high=5	[1, 7, 8, 9, 10, 5]
2	Swap elements	[1, 7, 8, 9, 10, 5]	5	Swap 10 and 5	[1, 7, 8, 9, 5, 10]
3	Place pivot	[1, 7, 8, 9, 5, 10]	5	Place pivot at correct position index=1	[1, 5, 8, 9, 7, 10]
4	Recursive call left	[1, 5, 8, 9, 7, 10]	-	Sort left sub-array low=0 high=0	[1, 5, 8, 9, 7, 10]
5	Recursive call right	[1, 5, 8, 9, 7, 10]	-	Sort right sub-array low=2 high=5	[1, 5, 8, 9, 7, 10]
6	Choose pivot	[1, 5, 8, 9, 7, 10]	10	Partition low=2 high=5	[1, 5, 8, 9, 7, 10]
7	Swap elements	[1, 5, 8, 9, 7, 10]	10	No swaps needed	[1, 5, 8, 9, 7, 10]
8	Place pivot	[1, 5, 8, 9, 7, 10]	10	Pivot placed at index=5	[1, 5, 8, 9, 7, 10]
9	Recursive call left	[1, 5, 8, 9, 7, 10]	-	Sort left sub-array low=2 high=4	[1, 5, 8, 9, 7, 10]
10	Choose pivot	[1, 5, 8, 9, 7, 10]	7	Partition low=2 high=4	[1, 5, 8, 9, 7, 10]
11	Swap elements	[1, 5, 8, 9, 7, 10]	7	Swap 9 and 7	[1, 5, 8, 7, 9, 10]
12	Place pivot	[1, 5, 8, 7, 9, 10]	7	Pivot placed at index=3	[1, 5, 7, 8, 9, 10]
13	Recursive call left	[1, 5, 7, 8, 9, 10]	-	Sort left sub-array low=2 high=2	[1, 5, 7, 8, 9, 10]
14	Recursive call right	[1, 5, 7, 8, 9, 10]	-	Sort right sub-array low=4 high=4	[1, 5, 7, 8, 9, 10]
15	Final sorted array	[1, 5, 7, 8, 9, 10]	-	-	[1, 5, 7, 8, 9, 10]

💡 All sub-arrays sorted or empty, recursion ends

Variable Tracker

Variable	Start	After Step 3	After Step 8	After Step 12	Final
arr	[10, 7, 8, 9, 1, 5]	[1, 5, 8, 9, 7, 10]	[1, 5, 8, 9, 7, 10]	[1, 5, 7, 8, 9, 10]	[1, 5, 7, 8, 9, 10]
pivot_index	N/A	1	5	3	N/A
low	0	0	2	2	N/A
high	5	5	5	4	N/A

Key Moments - 3 Insights

Why do we place the pivot at its correct position after partitioning?

Because after partitioning, all elements left of pivot are smaller and right are larger, so pivot is in its final sorted place (see steps 3, 8, 12).

Why do recursive calls stop when low >= high?

Because sub-arrays with zero or one element are already sorted, so no further sorting is needed (see steps 4, 5, 13, 14).

How does partitioning rearrange elements around the pivot?

Partitioning moves smaller elements to the left and larger to the right by swapping during traversal (see steps 1, 2, 11).

Visual Quiz - 3 Questions

Look at the execution table at step 3, what is the pivot index after placing the pivot?

A 1

B 5

C 0

D 3

💡 Hint

Check the 'pivot_index' value in variable_tracker after step 3.

At which step does the recursive call start sorting the left sub-array with low=0 and high=0?

A Step 5

B Step 4

C Step 9

D Step 13

💡 Hint

Look at the 'Operation' and 'Partitioning Action' columns in execution_table.

If the pivot chosen was always the last element, how would the array state change at step 1?

A Pivot would be 5 and array state same as shown

B Pivot would be 5 but array would be unchanged before partition

C Pivot would be 5 and array would be unchanged before partition

D Pivot would be 1 and array would be reversed

💡 Hint

Check the initial array and pivot choice in step 1 of execution_table.

Concept Snapshot

Quick Sort Algorithm:
- Pick a pivot element (commonly last element)
- Partition array so left < pivot < right
- Recursively sort left and right sub-arrays
- Base case: sub-array size 0 or 1
- Efficient average O(n log n) sorting
- In-place sorting with swaps

Full Transcript

Quick Sort works by choosing a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This process continues until the base case of sub-arrays with zero or one element is reached, which are already sorted. The pivot is placed at its correct sorted position after partitioning. The algorithm sorts the array in place by swapping elements during partitioning. The execution table shows each step of choosing pivots, partitioning, swapping, and recursive calls, with the array state updated accordingly. Variable tracking shows how the array and indices change after key steps. Key moments clarify why the pivot is placed and when recursion stops. The visual quiz tests understanding of pivot placement, recursive calls, and pivot choice effects. Quick Sort is a fast and efficient sorting algorithm widely used in practice.