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

Hoare Partition Scheme Pivot Selection

Mark
< Prev
Next >

Consider the following partition method, which implements Hoare’s partitioning scheme. Which of the following describes a significant performance pitfall of this implementation?

public class Sorter {
    public int partition(int[] data, int low, int high) {
        int pivot = data[low];
        int i = low - 1;
        int j = high + 1;
        while (true) {
            do {
                i++;
            } while (data[i] < pivot);
            do {
                j--;
            } while (data[j] > pivot);
            if (i >= j) return j;
            int temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }
}
A

Initializing i and j in this way inevitably leads to an infinite loop regardless of the input.

B

The pivot is updated inside the loop, causing its value to change and lead to incorrect partitioning.

C

The do-while loops might skip elements equal to the pivot, resulting in an unbalanced partition.

D

Choosing the first element as the pivot can lead to poor performance on nearly sorted arrays or arrays with many duplicates.

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|