Circlesort visualization!

[The Beez]

Hi 4tH-ers!

I've finally managed to visualize Circlesort! I had to do it in Coffeescript, which is not my favorite, but I did it. This is the first time you (and I) can actually see it work.

The results are like this:

Circle
# of swaps: 1224
# of inserts: 0
# of shifts per insert: 0
# of comparisons: 5684

Circle+
# of swaps: 945
# of inserts: 198
# of shifts per insert: 1
# of comparisons: 2983

Quick
# of swaps: 376
# of inserts: 0
# of shifts per insert: 0
# of comparisons: 2665

Sure, Quicksort beats it with less than a third of the swaps, but comparison-wise it's not too bad: only 10% difference!

Hans Bezemer

[The Beez]

Some more benchmarks on the optimized version of Circlesort (0.5 log2(n) iterations, followed by insertionsort).
- Quicksort is very good at avoiding swaps;
- CircInsert is much better in taking advantage of largely sorted arrays (especially inverted);

Random
Quick
# of swaps: 154

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 1128

Circinsert
# of swaps: 371
# of inserts: 98

# of shifts per insert: 1

# of comparisons: 1274

One out of order
Quick
# of swaps: 99

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 4950

Circinsert
# of swaps: 60
# of inserts: 98

# of shifts per insert: 0

# of comparisons: 1206

Reverse
Quick
# of swaps: 100

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 7085

Circinsert
# of swaps: 50

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 712

Sorted
Quick
# of swaps: 91

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 9307

Circinsert
# of swaps: 0

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 356

Sorted halfs
Quick
# of swaps: 150

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 3791

Circinsert
# of swaps: 155
# of inserts: 98

# of shifts per insert: 0

# of comparisons: 1205

Reverse sorted sequences
Quick
# of swaps: 163

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 1986

Circinsert
# of swaps: 254
# of inserts: 98

# of shifts per insert: 0

# of comparisons: 1195

Sorted sequences
Quicksort
# of swaps: 163

# of inserts: 0
# of shifts per insert: 0

# of comparisons: 1086

Circinsert
# of swaps: 275
# of inserts: 98

# of shifts per insert: 0

# of comparisons: 1225