Do you know where your variables are? PerlMonks

### Re: Smoothsort

by Laurent_R (Canon)
 on Sep 19, 2015 at 22:38 UTC ( #1142531=note: print w/replies, xml ) Need Help??

OMG, more that 200 lines of code for the implementation of a sorting algorithm in Perl! That's really inefficient in terms the work invested in coding (developer's hours are a costly resource) and of the risk of bugs, among other things.

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):

```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;
}
Just 17 lines of code, without any attempt to be particularly concise or clever.

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

Well yours of course but my coding loquacity is, I reckon, mostly to be blamed on my lack of wisdom and experience. Hence my coming here and my eagerness to find better and simpler ways to do that implementation

Create A New User
Node Status?
node history
Node Type: note [id://1142531]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (10)
As of 2020-11-24 12:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?