Quick Sort Algorithm 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 array and pivot?

DSA Java

int[] arr = {9, 3, 7, 6, 2, 8};
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, 7, 6, 2, 8, 9]

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

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

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

💡 Hint

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

The partition step moves all elements less than or equal to the pivot (8) to the left side, then places the pivot after them. The resulting array is [3, 7, 6, 2, 8, 9].

🧠 Conceptual

intermediate

Choosing Pivot in Quick Sort

Which of the following pivot choices can cause Quick Sort to degrade to worst-case performance on an already sorted array?

A Choosing the middle element as pivot

B Choosing the first element as pivot

C Choosing the median of first, middle, and last elements as pivot

D Choosing a random element as pivot

💡 Hint

Think about how the pivot divides the array in sorted input.

Choosing the first element as pivot on a sorted array causes unbalanced partitions, leading to O(n^2) time.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition Code

What error will the following Quick Sort partition code produce when run?

DSA Java

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) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    int temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;
    return i;
}

A No error, returns correct partition index

B ArrayIndexOutOfBoundsException

C Infinite loop

D Logical error: partition index is off by one

💡 Hint

Check the initialization of i and the loop boundaries carefully.

The code correctly partitions the array and returns the pivot index without errors.

❓ Predict Output

advanced

Final Sorted Array After Quick Sort

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

DSA Java

int[] arr = {5, 1, 4, 2, 8};
// Assume standard Quick Sort implementation is applied
// Output the sorted array

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

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

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

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

💡 Hint

Quick Sort sorts the array in ascending order.

Quick Sort sorts the array fully in ascending order: [1, 2, 4, 5, 8].

🧠 Conceptual

expert

Time Complexity of Quick Sort in Different Cases

Which statement correctly describes the time complexity of Quick Sort?

A Average case is O(n), worst case is O(n^2), best case is O(n log n)

B Average case is O(n^2), worst case is O(n log n), best case is O(n log n)

C Average case is O(n log n), worst case is O(n log n), best case is O(n)

D Average case is O(n log n), worst case is O(n^2), best case is O(n log n)

💡 Hint

Consider how balanced partitions affect complexity.

Quick Sort average and best cases are O(n log n) when partitions are balanced; worst case O(n^2) when partitions are unbalanced.

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