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.

Practice

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

easy

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

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

C. Insert elements one by one into a sorted list

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element 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 them to get the sorted array.

3. Final Answer:

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

4. Quick Check:

   Quick Sort = Divide and conquer using pivot [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
• Assuming 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. void partition(int arr[], int low, int high);

B. int partition(int arr[], int high, int low);

C. int partition(int arr, int low, int high);

D. int partition(int arr[], int low, int high);

Solution

1. Step 1: Check parameter types and order

   The partition function takes an array and two indices: low and high, both integers.

2. Step 2: Check return type

   It returns an integer index where the pivot finally lies.

3. Final Answer:

   int partition(int arr[], int low, int high); -> Option D

4. Quick Check:

   Correct function signature = int partition(int arr[], int low, int high); [OK]

Hint: Partition returns pivot index; parameters are array and two ints [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Swapping low and high parameters

3. What will be the output array after applying Quick Sort on arr = {4, 2, 7, 1} using the last element as pivot?

medium

A. [1, 2, 4, 7]

B. [1, 4, 2, 7]

C. [2, 1, 4, 7]

D. [7, 4, 2, 1]

Solution

1. Step 1: Partition with pivot 1

   Pivot is 1 (last element). After partition, array becomes [1, 2, 7, 4] with pivot at index 0.

2. Step 2: Recursively sort subarrays

   Left subarray is empty; right subarray [2,7,4] is sorted recursively to [2,4,7]. Final array is [1,2,4,7].

3. Final Answer:

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

4. Quick Check:

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

Hint: Pivot last element; sort left and right recursively [OK]

Common Mistakes:

• Not placing pivot correctly after partition
• Sorting only once without recursion
• Confusing 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], arr[j]);
      i++;
    }
  }
  swap(arr[i], arr[high]);
  return i;
}

medium

A. Swap should be done only if arr[j] <= pivot

B. Loop should run from j = low to j <= high

C. Initialization of i should be low - 1

D. Pivot should be arr[low] instead of arr[high]

Solution

1. Step 1: Check initialization of i

   In partition, i should start at low - 1 to track smaller elements correctly.

2. Step 2: Analyze loop and swaps

   Loop runs j from low to high-1 correctly; swap with arr[i+1] after loop is correct.

3. Final Answer:

   Initialization of i should be low - 1 -> Option C

4. Quick Check:

   i starts at low - 1 in partition [OK]

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

Common Mistakes:

• Starting i at low causes wrong partitioning
• Loop running to high causes out-of-bound swap
• Changing pivot position incorrectly

5. Given an array with many duplicate elements, which modification to Quick Sort helps improve performance?

hard

A. Always choose the first element as pivot

B. Use a three-way partitioning to separate less, equal, and greater elements

C. Skip sorting subarrays with size less than 5

D. Use Bubble Sort instead for duplicates

Solution

1. Step 1: Understand problem with duplicates

   Standard Quick Sort performs poorly with many duplicates due to repeated swaps.

2. Step 2: Apply three-way partitioning

   Three-way partitioning divides array into less than, equal to, and greater than pivot, reducing unnecessary work.

3. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option B

4. Quick Check:

   Three-way partitioning improves duplicates handling [OK]

Hint: Three-way partitioning handles duplicates efficiently [OK]

Common Mistakes:

• Choosing fixed pivot without considering duplicates
• Ignoring small subarrays optimization
• Switching to slower sorts unnecessarily