P is for Practical PerlMonks

### comment on

 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.

In reply to Re: Smoothsort by Laurent_R

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (4)
As of 2020-11-28 11:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?