SUMit Roster Software > Nut's Weekly > September 2002 > SortNederlands · Search...

Sort

 Monday, 2 September 2002 About Nut July 2002 August 2002
September 2002
Sort
QuickSort 4NF OONF News October 2002 November 2002
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.
  1. All numbers in the array are <=3.
  2. The pivot number remains 3 in deeper recursions.
  3. 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
  1. it splits series into parts of more equal size,
  2. it swaps more numbers into the right direction per recursion,
  3. which makes the recursion less deep.
Till next week, with a demo of this alternative Quicksort algorithm
Nut