Quick Sort Algorithm in DSA Java - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array around pivot

↓

Elements < pivot to left

↓

Elements > pivot to right

↓

Recursively apply Quick Sort

↓

Sort left part

↓

Combine results

↓

Sorted array

Quick Sort picks a pivot, partitions the array around it, then sorts left and right parts recursively.

Execution Sample

DSA Java

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);
  }
}

Sorts the array by partitioning around a pivot and recursively sorting subarrays.

Execution Table

Step	Operation	Pivot	Array State	Partition Indices	Action
1	Choose pivot	2	[5, 3, 8, 4, 2]	low=0, high=4	Pivot is last element 2
2	Partition start	2	[5, 3, 8, 4, 2]	i=-1, j=0	Compare arr[j] with pivot
3	Compare arr[0]=5 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=0	No swap, move j
4	Compare arr[1]=3 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=1	No swap, move j
5	Compare arr[2]=8 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=2	No swap, move j
6	Compare arr[3]=4 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=3	No swap, move j
7	Partition swap pivot	2	[2, 3, 8, 4, 5]	i=-1	Swap pivot with arr[i+1]
8	Recursive call left	-	[2, 3, 8, 4, 5]	low=0, high=-1	No action, base case
9	Recursive call right	-	[2, 3, 8, 4, 5]	low=1, high=4	Sort right subarray
10	Choose pivot	5	[2, 3, 8, 4, 5]	low=1, high=4	Pivot is 5
11	Partition start	5	[2, 3, 8, 4, 5]	i=0, j=1	Compare arr[j] with pivot
12	Compare arr[1]=3 < 5	5	[2, 3, 8, 4, 5]	i=1, j=1	Swap arr[i] and arr[j] (same)
13	Compare arr[2]=8 > 5	5	[2, 3, 8, 4, 5]	i=1, j=2	No swap, move j
14	Compare arr[3]=4 < 5	5	[2, 3, 8, 4, 5]	i=2, j=3	Swap arr[i] and arr[j] → [2,3,4,8,5]
15	Partition swap pivot	5	[2, 3, 4, 8, 5]	i=2	Swap pivot with arr[i+1] → [2,3,4,5,8]
16	Recursive call left	-	[2, 3, 4, 5, 8]	low=1, high=3	Sort left subarray
17	Choose pivot	4	[2, 3, 4, 5, 8]	low=1, high=3	Pivot is 4
18	Partition start	4	[2, 3, 4, 5, 8]	i=0, j=1	Compare arr[j] with pivot
19	Compare arr[1]=3 < 4	4	[2, 3, 4, 5, 8]	i=1, j=1	Swap arr[i] and arr[j] (same)
20	Compare arr[2]=4 == pivot	4	[2, 3, 4, 5, 8]	i=1, j=2	No swap, move j
21	Partition swap pivot	4	[2, 3, 4, 5, 8]	i=1	Swap pivot with arr[i+1] (same)
22	Recursive call left	-	[2, 3, 4, 5, 8]	low=1, high=1	Base case, no action
23	Recursive call right	-	[2, 3, 4, 5, 8]	low=3, high=3	Base case, no action
24	Recursive call right	-	[2, 3, 4, 5, 8]	low=4, high=4	Base case, no action
25	End	-	[2, 3, 4, 5, 8]	-	Array fully sorted

💡 All subarrays sorted or base cases reached, recursion ends

Variable Tracker

Variable	Start	After Step 7	After Step 15	After Step 21	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	2	2	5	4	4
i (partition index)	-1	-1	2	1	1
low	0	1	1	1	1
high	4	4	4	3	3

Key Moments - 3 Insights

Why does the pivot start as the last element in the current subarray?

The pivot is chosen as the last element to simplify partitioning logic, as seen in Step 1 and Step 10 where the pivot is arr[high]. This consistent choice helps in partitioning the array around it.

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

Swapping arr[i] and arr[j] when arr[j] < pivot ensures all smaller elements move to the left side. This is shown in Steps 12 and 14 where swaps happen only for elements less than pivot.

What happens when the subarray has one or zero elements?

When low >= high, the recursion stops (base case), as in Steps 8, 22, 23, and 24. This prevents unnecessary sorting of already sorted or empty subarrays.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after Step 7?

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

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

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

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

💡 Hint

Check the 'Array State' column at Step 7 in the execution_table.

At which step does the pivot 5 get swapped with another element?

A Step 15

B Step 14

C Step 13

D Step 12

💡 Hint

Look for 'Partition swap pivot' operation involving pivot 5 in the execution_table.

If the pivot was chosen as the first element instead of the last, how would the partition indices change at Step 2?

A i would start at low instead of -1

B i would start at low - 1

C i would start at high

D i would start at 0

💡 Hint

Partition index i usually starts one less than low when pivot is last element; changing pivot affects this initialization.

Concept Snapshot

Quick Sort Algorithm:
- Choose pivot (commonly last element)
- Partition array: smaller left, larger right
- Recursively sort left and right subarrays
- Base case: subarray size ≤ 1
- Efficient average O(n log n) sorting

Full Transcript

Quick Sort works by picking a pivot element, usually the last in the current subarray. It then partitions the array so that elements smaller than the pivot go to the left, and larger go to the right. This partitioning uses two pointers: i tracks the boundary of smaller elements, and j scans through the array. When arr[j] is smaller than the pivot, it swaps with arr[i+1]. After partitioning, the pivot is placed in its correct sorted position. The algorithm then recursively sorts the left and right parts until the base case of subarrays with one or zero elements is reached. This process sorts the entire array efficiently.

Practice

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

easy

A. Insert elements one by one into their correct position

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

C. Merge two sorted arrays into one sorted array

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

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 D

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
• Assuming Quick Sort inserts elements one by one

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

easy

A. int partition(int arr[], low, high)

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

C. void partition(int[] arr, int low, int high)

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

Solution

1. Step 1: Check Java method declaration syntax

   Java methods must specify access modifier, return type, method name, and parameter types with names.

2. Step 2: Validate each option

   public int partition(int[] arr, int low, int high) correctly declares a public method returning int with parameters typed and named properly.

3. Final Answer:

   public int partition(int[] arr, int low, int high) -> Option B

4. Quick Check:

   Java method syntax = public int partition(int[] arr, int low, int high) [OK]

Hint: Remember Java method syntax: access + return type + name + parameters [OK]

Common Mistakes:

• Omitting return type
• Missing parameter types
• Incorrect order of parameters

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

medium

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

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

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

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

Solution

1. Step 1: Choose pivot and partition

   Pivot is last element 2. Move elements smaller than 2 to left.

2. Step 2: Rearrange array

   No elements smaller than 2, so swap 2 with first element 8. Result: [2, 3, 6, 7, 8]

3. Step 3: Check order after partition

   Elements less than pivot (none) are left, others right. No further swaps in first partition.

4. Final Answer:

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

5. Quick Check:

   Pivot 2 placed correctly, smaller left, larger right [OK]

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

Common Mistakes:

• Not swapping pivot correctly
• Assuming all smaller elements are sorted immediately
• Confusing pivot position after partition

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. Pivot should be arr[low] instead of arr[high]

B. Loop condition should be j <= high

C. Variable i should start at low - 1

D. Swap should happen only if arr[j] <= pivot

Solution

1. Step 1: Analyze initialization of i

   In Lomuto partition, i starts at low - 1 to track smaller elements index before loop.

2. Step 2: Check loop and swaps

   Starting i at low causes incorrect swaps and pivot placement.

3. Final Answer:

   Variable i should start at low - 1 -> Option C

4. Quick Check:

   i = low - 1 for correct partition [OK]

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

Common Mistakes:

• Starting i at low causes wrong partition
• Changing pivot position incorrectly
• Using wrong loop bounds

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

hard

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

B. Always pick the first element as pivot

C. Use Bubble Sort instead for duplicates

D. Skip sorting duplicates by checking each element

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. Step 3: Evaluate other options

   Picking first element or skipping sorting duplicates doesn't improve performance reliably; Bubble Sort is inefficient.

4. Final Answer:

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

5. Quick Check:

   Three-way partitioning = better with duplicates [OK]

Hint: Use three-way partitioning for arrays with many duplicates [OK]

Common Mistakes:

• Picking fixed pivot without randomization
• Ignoring duplicates in partitioning
• Switching to inefficient sorts unnecessarily