Quick Sort as Divide and Conquer in DSA Java

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, and then combines them to get a sorted list.

Analogy: Imagine sorting a deck of cards by picking one card as a divider, putting smaller cards to the left and bigger cards to the right, then sorting each side separately.

Array: [7, 2, 9, 4, 3]
Pivot chosen: 4
Partitioned: [2, 3] -> 4 -> [7, 9]

Dry Run Walkthrough

Input: array: [7, 2, 9, 4, 3]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot 3 (last element), partition array around pivot

[2] -> 3 -> [9, 4, 7]

Why: Pivot divides array into smaller and larger elements

Step 2: Recursively quick sort left part [2]

[2]

Why: Single element is already sorted

Step 3: Recursively quick sort right part [9, 4, 7], choose pivot 7

[4] -> 7 -> [9]

Why: Partition right part around pivot 7

Step 4: Recursively quick sort left part [4]

[4]

Why: Single element is already sorted

Step 5: Recursively quick sort right part [9]

[9]

Why: Single element is already sorted

Step 6: Combine all sorted parts

[2, 3, 4, 7, 9]

Why: All parts sorted and combined to get final sorted array

Result:

Final sorted array: [2, 3, 4, 7, 9]

Annotated Code

DSA Java

public class QuickSort {

    // Function to perform quick sort on array from low to high indices
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get pivot index
            int pivotIndex = partition(arr, low, high);

            // Recursively sort elements before pivot
            quickSort(arr, low, pivotIndex - 1);

            // Recursively sort elements after pivot
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Partition function to place pivot at correct position
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // choose last element as pivot
        int i = low - 1; // index of smaller element

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // place pivot after smaller elements
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // return pivot index
    }

    // Driver code to test quick sort
    public static void main(String[] args) {
        int[] arr = {7, 2, 9, 4, 3};
        quickSort(arr, 0, arr.length - 1);

        // Print sorted array
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

if (low < high) {

check if subarray has more than one element to sort

int pivotIndex = partition(arr, low, high);

partition array and get pivot position

quickSort(arr, low, pivotIndex - 1);

recursively sort left subarray

quickSort(arr, pivotIndex + 1, high);

recursively sort right subarray

for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap arr[i] and arr[j]; } }

move elements smaller or equal to pivot to left side

swap arr[i + 1] and arr[high];

place pivot after smaller elements

Output

2 3 4 7 9 

Complexity Analysis

Time: O(n log n) average case because the array is divided into halves recursively and each element is compared once per level

Space: O(log n) due to recursive call stack in average case

vs Alternative: Compared to bubble sort's O(n^2), quick sort is much faster on average due to divide and conquer splitting

Edge Cases

empty array

function returns immediately without changes

DSA Java

if (low < high) {

array with one element

function returns immediately as subarray size is 1

DSA Java

if (low < high) {

array with all elements equal

All elements go to left (<= pivot), right empty, unbalanced partitions lead to O(n^2) worst case

DSA Java

if (arr[j] <= pivot) {

When to Use This Pattern

When you see a problem asking to sort or order elements efficiently, and it mentions divide and conquer, think of Quick Sort because it splits the problem into smaller parts around a pivot.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping elements properly during partition
Fix: Always choose pivot consistently (e.g., last element) and swap elements to ensure smaller elements are left of pivot

Mistake: Not updating indices correctly in partition leading to infinite recursion
Fix: Increment index i only when smaller element found and swap correctly to avoid infinite loops

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting subarrays recursively.

Use Quick Sort when you want an efficient average-case sorting algorithm with divide and conquer.

The key insight is partitioning the array so that smaller elements go left and larger go right around a pivot.

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