CODEWITHSUNDEEP
algorithmpartitioningquicksort
Michael
Michael

Reputation: 42050

Algorithms for 3-way partitioning

The 3-way partitioning splits an array into 3 sub-arrays: elements < pivot, elements == pivot, elements > pivot.

We can use the well-known solution for E. Dijkstra's "Dutch Flag Problem" to do that but Bentley and McIlroy suggest another way (see section #22, "Fast three-way partitioning")

Unfortunately I do not understand how their algorithm is better (faster). Could anybody explain it slowly?

Upvotes: 1

Views: 1475

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183888

It uses fewer swaps on average, at least while there are not too few different elements in the array.

The "Dutch Flag" algorithm uses one swap per element not equal to the pivot, so that's

n - multiplicity(pivot)

swaps.

The alternative, which swaps the elements equal to the pivot to the ends of the array first, swaps each element equal to the pivot twice (once to one end, and finally to the middle), and swaps pairs a[i], a[j] with i < j and a[j] < pivot < a[i], that's

2*multiplicity(pivot) + count(bad_pairs)

swaps. The number of bad pairs cannot be more than (n - multiplicity(pivot))/2 and is usually (random array) smaller, off the top of my head, I'd expect something like (n-multiplicity(pivot))/4 or less on average. So if multiplicity(pivot) < n/5, the alternative is guaranteed to use fewer swaps, and if my estimate is right, it will on average use fewer swaps if multiplicity(pivot) < 3*n/11.

So if you know a priori that there are only very few (<= 5 or so) distinct elements in the array, I think "Dutch Flag" will be superior, but in general, the alternative will use fewer swaps until the parts to be sorted have become rather small.

Upvotes: 2

Related Questions