Quick Sort as Divide and Conquer in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output array after the partition step in Quick Sort for the given code snippet?

DSA Java

int[] arr = {9, 3, 7, 6, 2};
int pivot = arr[arr.length - 1];
int i = -1;
for (int j = 0; j < arr.length - 1; 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[arr.length - 1];
arr[arr.length - 1] = temp;
System.out.println(java.util.Arrays.toString(arr));

A [3, 2, 7, 6, 9]

B [2, 3, 6, 7, 9]

C [2, 3, 7, 6, 9]

D [3, 7, 6, 2, 9]

💡 Hint

Focus on how elements less than the pivot are moved to the left side.

The partition step moves all elements smaller than the pivot (2) to the left. The pivot is then placed after these elements. The resulting array is [2, 3, 7, 6, 9].

🧠 Conceptual

intermediate

Understanding Quick Sort's Divide and Conquer

Which statement best describes the divide and conquer approach in Quick Sort?

A Quick Sort divides the array into two parts around a pivot and recursively sorts each part.

B Quick Sort merges two sorted arrays into one sorted array.

C Quick Sort uses a heap to repeatedly extract the smallest element.

D Quick Sort sorts the array by repeatedly swapping adjacent elements.

💡 Hint

Think about how Quick Sort breaks down the problem into smaller parts.

Quick Sort picks a pivot, partitions the array into elements less and greater than the pivot, then recursively sorts these parts.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition Code

What error will occur when running this Quick Sort partition code snippet?

DSA Java

int[] arr = {4, 5, 3, 7, 2};
int pivot = arr[arr.length];
int i = -1;
for (int j = 0; j < arr.length - 1; 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[arr.length - 1];
arr[arr.length - 1] = temp;

A ArrayIndexOutOfBoundsException

B NullPointerException

C No error, runs correctly

D ClassCastException

💡 Hint

Check the pivot assignment line carefully.

Accessing arr[arr.length] causes ArrayIndexOutOfBoundsException because array indices go from 0 to arr.length - 1.

❓ Predict Output

advanced

Final Sorted Array After Quick Sort

What is the final sorted array after running Quick Sort on the array below?

DSA Java

int[] arr = {10, 7, 8, 9, 1, 5};
// Assume Quick Sort is correctly implemented and called on arr
// Print the array after sorting
System.out.println(java.util.Arrays.toString(arr));

A [1, 7, 5, 8, 9, 10]

B [10, 9, 8, 7, 5, 1]

C [5, 1, 7, 8, 9, 10]

D [1, 5, 7, 8, 9, 10]

💡 Hint

Quick Sort sorts the array in ascending order.

Quick Sort sorts the array from smallest to largest, so the final sorted array is [1, 5, 7, 8, 9, 10].

🧠 Conceptual

expert

Time Complexity of Quick Sort in Worst Case

What is the worst-case time complexity of Quick Sort and when does it occur?

A O(n log n), when the pivot divides the array evenly

B O(n^2), when the pivot is always the smallest or largest element

C O(n), when the array is already sorted

D O(log n), when the pivot is chosen randomly

💡 Hint

Consider what happens if the pivot does not split the array well.

The worst case happens when the pivot is always the smallest or largest element, causing unbalanced partitions and O(n^2) time.

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