Hoare Partition Scheme Pivot Selection

Question

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

```java
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;
        }
    }
}
```

Accepted Answer

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

Answer

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

Answer

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

Answer

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

Question Leaderboard