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!
**~½N**compares when all keys equal.^{2}- 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 item`a[lo]`

- Scan
`i`

from left to right.`(a[i] < v)`

: exchange`a[lt]`

with`a[i]`

; increment both`lt`

and`i`

`(a[i] > v)`

: exchange`a[gt]`

with`a[i]`

; decrement`gt`

`(a[i] == v)`

: increment`i`