Quick Sort
(gamedev.net/...)
is a pretty sorting algorithm,
invented back in 1962 by professor C.A.R. Hoare
(...infcharles.html).
- It sorts inside the array itself,
using only a couple of pointers that work outside in.
- It uses powerful recursion to split, split and split the series of numbers
(...sortieren/quick...).
- It is quite fast.
Step taken |
<=4 |
to do |
>4 |
4 as pivot |
|
5, 3, 4, 2, 1
|
|
1 and 5 swapped |
1 |
3, 4, 2 |
5 |
3, 4, and 2 to left |
1, 3, 4, 2 |
|
5 |
3 as pivot |
<=3 |
to do |
>3 |
|
5 |
1 and 3 to left |
1, 3 |
4, 2 |
|
|
5 |
4 and 2 swapped |
1, 3, 2 |
|
4 |
|
5 |
3 as pivot |
<=3 |
to do |
>3 |
|
4 |
|
5 |
|
1, 3, 2 |
|
|
4 |
|
5 |
1, 3, 2 to left? |
1, 3, 2 |
|
|
|
4 |
|
5 |
Yet, I have never been able to understand how Quick Sort can work on the array {1, 3, 2}, having '3' as pivot.
- All numbers in the array are <=3.
- The pivot number remains 3 in deeper recursions.
- The recursion never ends, never produces any result.
Alternative
An elegant alternative:
Step taken |
<=4 |
to do |
>=4 |
4 as pivot |
|
5, 3, 4, 2, 1
|
|
1 and 5 swapped |
1 |
3, 4, 2 |
5 |
3 to left |
1, 3 |
4, 2 |
5 |
2 and 4 swapped |
1, 3, 2 |
|
4, 5 |
3 as pivot |
<=3 |
to do |
>=3 |
|
4, 5 |
1 to left |
1 |
3, 2 |
|
|
4, 5 |
3 and 2 swapped |
1, 2 |
|
3 |
|
4, 5 |
- Smaller numbers still move left.
- Larger numbers still move right.
- But all equal numbers
are candidate for a swap.
So, the numbers that
equal the pivot,
can move both left and right.
That seems odd and indecisive, resulting in inefficiency.
But on the contrary, it
speeds up
the sorting because
- it splits series into parts of more equal size,
- it swaps more numbers into the right direction per recursion,
- which makes the recursion less deep.
Till
next week, with a
demo of this alternative Quicksort algorithm
Nut
|