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.
- Part 1 - Basic Implementation
- Part 2 - Selection Problems
- Part 3 - 3-way Partitioning
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
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
- Let
v
be partitioning itema[lo]
- Scan
i
from left to right.(a[i] < v)
: exchangea[lt]
witha[i]
; increment bothlt
andi
(a[i] > v)
: exchangea[gt]
witha[i]
; decrementgt
(a[i] == v)
: incrementi