Are you taking CLEP classes? Try clep.ai
| preferred AP College board partner for AP classes
AP Computer Science A/Unit 4: Iteration
Start Practice TestPractice Test
About Exam
hard

QuickSort Partition With Duplicate Values

Mark
< Prev
Next >

Consider the following partition method, which is used in a QuickSort algorithm. What potential issue arises when the array to be partitioned contains elements equal to the pivot value?

public class QuickSortPartition {
    public static int partition(int[] arr, int low, int high) {
         int pivot = arr[high];
         int i = low;
         int j = high - 1;
         while(i < j) {
             while(arr[i] < pivot) {
                 i++;
             }
             while(arr[j] > pivot) {
                 j--;
             }
             if(i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
             }
         }
         int temp = arr[i];
         arr[i] = arr[high];
         arr[high] = temp;
         return i;
    }
    
    public static void main(String[] args) {
         int[] numbers = {3, 9, 4, 8, 5, 7, 6};
         int pos = partition(numbers, 0, numbers.length - 1);
         System.out.println("Pivot position: " + pos);
         System.out.println(java.util.Arrays.toString(numbers));
    }
}
A

The pivot is improperly swapped with the last element, which is never compared.

B

The code does not properly handle elements equal to the pivot, potentially resulting in an incorrect partition.

C

The use of nested while loops causes some elements to be skipped during comparison.

D

The pivot is selected as the first element instead of a randomized element, leading to poor performance.

Hint
Did You Know?
Explain Why
Explain All Answers
Check Answer
Show Correct Answer
Report Question

Question Leaderboard

Not enough data yet to show leaderboard.

AI Tutor

How can I help?

APFIVE © 2020.
Email: apfive@apfive.org|Privacy Policy|