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!
**~½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`

# Java Implementation

```
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;
while (i <= gt)
{
int cmp = a[i].compareTo(v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
```

Quick Sort with 3-way partitioning is even shorter (and harder to imagine). I gave one compliment to the brain that could thought of those above solutions.