in reply to Smoothsort
Just as a counterexample, this is a Perl implementation of another "exotic" sort algorithm, comb sort (or Dobosiewicz sort), I made almost 3 years ago, essentially for fun, and published at the time on the French version of Wikipedia where it can still be found (https://fr.wikipedia.org/wiki/Tri_%C3%A0_peigne):
Just 17 lines of code, without any attempt to be particularly concise or clever.sub comb_sort { my @v = @_; my $max = scalar (@v); my $gap = $max; while (1) { my $swapped = 0; $gap = int ($gap / 1.3); $gap = 11 if $gap == 10 or $gap == 9; # (Combsort11 optimization) $gap = 1 if $gap < 1; my $lmax = $max - $gap - 1; foreach my $i (0..$lmax) { ($v[$i], $v[$i+$gap], $swapped) = ($v[$i+$gap], $v[$i], 1) i +f $v[$i] > $v[$i+$gap]; } last if $gap == 1 and $swapped == 0; } return @v; }
Between your 220-line code and my 17-line code, which one would you prefer to debug?
And, BTW, my version of comb sort seems to be correct (tested with a number of samples of tens of thousands of values) and behaves fairly well in terms of performance: from my own benchmark, it is slightly faster -(x 1.35) than a pure Perl implementation of merge sort for random input, and much faster (x 20) than quick sort and Shell sort for skewed data (e.g. almost sorted, or almost sorted backward input) leading to 0(nē) worst case performance for those latter algorithms.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Smoothsort
by QuillMeantTen (Friar) on Sep 19, 2015 at 22:42 UTC |