Quick Sort as Divide and Conquer in DSA Java - Execution Trace

Concept Flow - Quick Sort as Divide and Conquer

Start: Array to sort

↓

Choose pivot element

↓

Partition array around pivot

↓

Left sub-array < pivot

↓

Recursively quick sort left

↓

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

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 temp = a[i + 1];
  a[i + 1] = a[high];
  a[high] = temp;
  return i + 1;
}

This code sorts the array by choosing a pivot, partitioning, and recursively sorting sub-arrays.

Execution Table

Step	Operation	Pivot	Array State	Partition Indices	Action
1	Start quickSort(0,4)	-	[5, 3, 8, 4, 2]	-	Choose pivot=2 (last element)
2	Partition around pivot=2	2	[5, 3, 8, 4, 2]	i=-1, j=0 to 3	Swap elements <=2 with left side
3	Compare arr[0]=5 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=0	No swap, i stays -1
4	Compare arr[1]=3 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=1	No swap, i stays -1
5	Compare arr[2]=8 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=2	No swap, i stays -1
6	Compare arr[3]=4 > 2	2	[5, 3, 8, 4, 2]	i=-1, j=3	No swap, i stays -1
7	Swap pivot with arr[i+1]	2	[2, 3, 8, 4, 5]	i=-1	Pivot placed at index 0
8	Recurse quickSort(0,-1)	-	[2, 3, 8, 4, 5]	-	Base case, return
9	Recurse quickSort(1,4)	-	[2, 3, 8, 4, 5]	-	Sort right sub-array
10	Choose pivot=5	5	[2, 3, 8, 4, 5]	-	Pivot is last element 5
11	Partition around pivot=5	5	[2, 3, 8, 4, 5]	i=0, j=1 to 3	Swap elements <=5 to left
12	Compare arr[1]=3 <= 5	5	[2, 3, 8, 4, 5]	i=0, j=1	Swap arr[i+1] and arr[j], i=1
13	Compare arr[2]=8 > 5	5	[2, 3, 8, 4, 5]	i=1, j=2	No swap, i stays 1
14	Compare arr[3]=4 <= 5	5	[2, 3, 8, 4, 5]	i=1, j=3	Swap arr[i+1] and arr[j], i=2
15	Swap pivot with arr[i+1]	5	[2, 3, 4, 5, 8]	i=2	Pivot placed at index 3
16	Recurse quickSort(1,2)	-	[2, 3, 4, 5, 8]	-	Sort left sub-array
17	Choose pivot=4	4	[2, 3, 4, 5, 8]	-	Pivot is last element 4
18	Partition around pivot=4	4	[2, 3, 4, 5, 8]	i=0, j=1	Swap elements <=4 to left
19	Compare arr[1]=3 <= 4	4	[2, 3, 4, 5, 8]	i=0, j=1	Swap arr[i+1] and arr[j], i=1
20	Swap pivot with arr[i+1]	4	[2, 3, 4, 5, 8]	i=1	Pivot placed at index 2
21	Recurse quickSort(1,1)	-	[2, 3, 4, 5, 8]	-	Base case, return
22	Recurse quickSort(3,2)	-	[2, 3, 4, 5, 8]	-	Base case, return
23	Recurse quickSort(4,4)	-	[2, 3, 4, 5, 8]	-	Base case, return
24	All recursive calls done	-	[2, 3, 4, 5, 8]	-	Array fully sorted

💡 All sub-arrays reduced to base cases where low >= high, recursion ends

Variable Tracker

Variable	Start	After Step 7	After Step 15	After Step 20	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	-
Partition i	-	-1	2	1	-
Partition j	-	3	3	1	-

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, swapping places pivot correctly so left side < pivot and right side > pivot (see steps 7, 15, 20).

Why does recursion stop when low >= high?

Because sub-arrays of size 0 or 1 are already sorted, so no further sorting is needed (see steps 8, 21, 22, 23).

Why do we choose the last element as pivot?

Choosing the last element is a simple pivot selection method; it helps partition the array around it (see steps 1, 10, 17).

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 [5, 3, 4, 8, 2]

💡 Hint

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

At which step does the pivot get placed at index 3?

A Step 7

B Step 20

C Step 15

D Step 10

💡 Hint

Look for 'Pivot placed at index 3' in the 'Action' column.

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 second element to the end

B Partition would not change at all

C Pivot would be swapped with the last element immediately

D Recursion would stop earlier

💡 Hint

Think about how partition compares elements relative to the pivot position.

Concept Snapshot

Quick Sort divides array by pivot.
Partition places pivot correctly.
Recursively sort left and right parts.
Base case: sub-array size ≤ 1.
Efficient divide and conquer sorting.

Full Transcript

Quick Sort works by choosing a pivot element, usually the last element in the current array segment. It then partitions the array so that all elements less than or equal to the pivot are on the left, and all greater elements are on the right. This is done by moving a pointer i to track the boundary of smaller elements and swapping elements as needed. After partitioning, the pivot is swapped into its correct position at i+1. The algorithm then recursively applies the same process to the left and right sub-arrays until the base case of sub-arrays with zero or one element is reached. The execution table shows each step of partitioning and recursion, with the array state and pointer positions. Key moments include understanding why the pivot is swapped at the end of partition and why recursion stops when sub-arrays are small. The visual quiz tests understanding of array states after swaps and the effect of pivot choice. This divide and conquer approach efficiently sorts the array in place.

Practice

1. What is the main idea behind the Quick Sort algorithm as a divide and conquer method?

easy

A. Divide the array into smaller parts, sort them, and combine the results

B. Sort the array by repeatedly swapping adjacent elements

C. Use extra space to merge two sorted arrays

D. Find the maximum element and place it at the end repeatedly

Solution

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

   Quick Sort divides the array into parts based on a pivot, sorts each part separately.

2. Step 2: Recognize the combining step

   After sorting parts, the array is combined naturally as parts are sorted in place.

3. Final Answer:

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

4. Quick Check:

   Divide and conquer = split, sort, combine [OK]

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

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort uses extra space like Merge Sort
• Believing Quick Sort only swaps adjacent elements

2. Which of the following is the correct way to choose a pivot in Quick Sort in Java?

easy

A. int pivot = arr[length / 2];

B. int pivot = arr[arr.length / 2];

C. int pivot = arr[arr.length];

D. int pivot = arr[-1];

Solution

1. Step 1: Identify valid pivot index

   Array indices go from 0 to length-1, so middle index is length/2.

2. Step 2: Check each option

   A uses length (undefined, invalid), B uses arr.length (out of bounds), C uses middle element (valid), D uses negative index (invalid in Java).

3. Final Answer:

   int pivot = arr[arr.length / 2]; -> Option B

4. Quick Check:

   Pivot index must be within 0 to length-1 [OK]

Hint: Pivot index must be valid array index [OK]

Common Mistakes:

• Using arr.length as index (out of bounds)
• Using negative indices (not allowed in Java)
• Always choosing first element without reason

3. What will be the output array after the first partition step of Quick Sort on int[] arr = {4, 7, 2, 9, 1} if pivot is chosen as the first element?

medium

A. [2, 1, 4, 7, 9]

B. [1, 2, 4, 9, 7]

C. [4, 7, 2, 9, 1]

D. [9, 7, 4, 2, 1]

Solution

1. Step 1: Choose pivot and partition

   Pivot = 4. Elements less than 4 go left, greater go right.

2. Step 2: Rearrange array after partition

   Left side: 2,1; pivot:4; right side:7,9. So array becomes [2, 1, 4, 7, 9].

3. Final Answer:

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

4. Quick Check:

   Partition arr around pivot 4 = [2,1,4,7,9] [OK]

Hint: Partition places pivot between smaller and larger elements [OK]

Common Mistakes:

• Not moving elements smaller than pivot to left
• Leaving array unchanged after partition
• Placing pivot at wrong position

4. Identify the error in this Quick Sort partition code snippet in Java:

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

medium

A. Variable i should start at low, not low - 1

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

C. Loop should run until j < high, not j <= high

D. Swap logic is incorrect

Solution

1. Step 1: Analyze loop boundary

   The loop runs j from low to high inclusive, but arr[high] is pivot and should not be compared inside loop.

2. Step 2: Correct loop condition

   Loop should run j from low to high-1 to avoid swapping pivot with itself.

3. Final Answer:

   Loop should run until j < high, not j <= high -> Option C

4. Quick Check:

   Partition loop excludes pivot index [OK]

Hint: Loop excludes pivot index during partition [OK]

Common Mistakes:

• Including pivot in partition loop
• Starting i at wrong index
• Changing pivot selection unnecessarily

5. Given the array {10, 80, 30, 90, 40, 50, 70}, if Quick Sort always chooses the last element as pivot, what is the sequence of pivot values chosen during the entire sorting process?

hard

A. [70, 50, 40, 30, 10, 90, 80]

B. [70, 90, 80, 50, 40, 10, 30]

C. [70, 90, 80, 50, 40, 30, 10]

D. [70, 50, 40, 30, 10, 80, 90]

Solution

1. Step 1: Identify pivots chosen at each recursive call

   First pivot: last element 70. After partition, left subarray ends at 50, right subarray ends at 80.

2. Step 2: Continue choosing last element as pivot in subarrays

   Next pivots: 50 (left), then 40, then 30, then 10; right subarray pivots: 80, then 90.

3. Final Answer:

   [70, 50, 40, 30, 10, 80, 90] -> Option D

4. Quick Check:

   Last element pivot sequence matches [OK]

Hint: Pivot is always last element in current subarray [OK]

Common Mistakes:

• Mixing pivot order with sorted array order
• Choosing first element as pivot instead
• Ignoring recursive calls on subarrays