Quick Sort as Divide and Conquer in DSA Java - Build from Scratch

Quick Sort as Divide and Conquer

📖 Scenario: You are helping a small bookstore organize their inventory by sorting the list of book prices. They want the prices sorted from lowest to highest so they can easily find deals and manage stock.

🎯 Goal: Build a Java program that uses the Quick Sort algorithm to sort an array of book prices in ascending order. You will implement the divide and conquer approach step-by-step.

📋 What You'll Learn

Create an integer array called prices with the exact values: 45, 23, 89, 12, 67, 34, 78

Create an integer variable called pivotIndex to help with partitioning

Implement the partition method that rearranges elements around the pivot

Implement the quickSort method that recursively sorts the array

Print the sorted prices array in the format: 12 -> 23 -> 34 -> 45 -> 67 -> 78 -> 89 -> null

💡 Why This Matters

🌍 Real World

Sorting prices helps stores organize inventory and find deals quickly.

💼 Career

Understanding Quick Sort is important for software engineers working with efficient data processing and algorithms.

1

Create the initial array of book prices

Create an integer array called prices with these exact values: 45, 23, 89, 12, 67, 34, 78

DSA Java

# Create the prices array with the given values
# Your code here

Hint

Use int[] prices = { ... }; to create the array with the exact numbers.

2

Add a pivot index variable for partitioning

Inside the main method, create an integer variable called pivotIndex and set it to 0 to help with partitioning

DSA Java

public class QuickSort {
    public static void main(String[] args) {
        int[] prices = {45, 23, 89, 12, 67, 34, 78};
        // Create pivotIndex variable
        // Your code here
    }
}

Hint

Declare int pivotIndex = 0; inside the main method.

3

Implement the Quick Sort and Partition methods

Add a static method partition that takes an integer array arr, low, and high indexes and returns the pivot position after rearranging elements. Then add a static method quickSort that recursively sorts the array using partition. Call quickSort(prices, 0, prices.length - 1) inside main.

DSA Java

public class QuickSort {
    public static void main(String[] args) {
        int[] prices = {45, 23, 89, 12, 67, 34, 78};
        int pivotIndex = 0;
        // Call quickSort here
        // Your code here
    }

    // Add partition method here
    // Your code here

    // Add quickSort method here
    // Your code here
}

Hint

Use the last element as pivot in partition. Swap elements smaller than pivot to the left. Recursively call quickSort on left and right parts.

4

Print the sorted array

Add code inside main to print the sorted prices array in this exact format: 12 -> 23 -> 34 -> 45 -> 67 -> 78 -> 89 -> null

DSA Java

public class QuickSort {
    public static void main(String[] args) {
        int[] prices = {45, 23, 89, 12, 67, 34, 78};
        int pivotIndex = 0;
        quickSort(prices, 0, prices.length - 1);
        // Print the sorted array in the format: 12 -> 23 -> 34 -> 45 -> 67 -> 78 -> 89 -> null
        // Your code here
    }

    public static 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;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

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

Hint

Use a for loop to print each element followed by " -> ", then print "null" at the end.

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