Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, I remember nothing about it because I haven’t touched it for the long time.
Quick Sort - Duplicate Keys Problem
- Quick Sort goes quadratic unless partitioning stops on equal keys!
- ~½N2 compares when all keys equal.
- B A A B A B B B C C C
- A A A A A A A A A A A
- Solve by using 3-way partitioning
Partition array into 3 parts so that:
- Entries between lt and gt equal to partition item v
- No larger entries to left of lt
- No smaller entries to right of gt
vbe partitioning item
ifrom left to right.
(a[i] < v): exchange
a[i]; increment both
(a[i] > v): exchange
(a[i] == v): increment