Golfed sort by debian version number I wrote some perl to sort by debian package version number (specification here). Whilst readable, it was disappointingly long (114 lines, 2042 characters) - shocking. So this challenge is to produce the shortest program (in perl or otherwise) which takes debian package version numbers on STDIN separated by \n, sorts them, and puts the output on STDOUT separated by \n.

You can produce an dataset of debian versions numbers on a debian/ubuntu box by:

apt-cache madison . | perl -n -e 'print "$1\n" if /^\S+\s+\|\s+(\S+)\s+/;'


For those not on Debian / Ubuntu I've put a random selection of 1000 here. The sorted version of this sample is here. The md5sum of the unsorted and sorted versions (check they each end with a \n) are:

5ffd12d3f59b06619a712e92791c0dfd  input.sample
e6b2d03ddfd9491c5bdf2594a5aa82e5  output.sample


(note as Ventero points out in the comments, there are certain equivalent version numbers, e.g. lines 135-138 out of the output, where 08 and 8 are equivalent and thus the sort order is arbitrary)

For the purposes of verifying your input, you can install Debian::Dpkg::Version from CPAN and use the following to test:

#!/usr/bin/perl

use strict;
use warnings;
use Debian::Dpkg::Version;

my @input;

while (&lt;&gt;)
{
    chomp;
    push @input, $_;
}

my @output = sort version_compare (@input);
print join("\n", @output)."\n";


The following test data is thus sorted in the correct order, and (I believe) only contains lines complying with the Debian spec above, with each version being distinct:

0~~-~~
0~~-~
0~-~~
0~-~
0~-0
0-0
0-1
0-02
3-0
04-0
04a-0
5-0
04:3-0
5:3-0
06:3-0
06:3a-0
06:3a-01
06:3a-3~
06:3a-3
6:3a-04
06:3a-05
06:3.-0
06:3:a
06:3:a-01
06:3:a-05


The rules are:


Package name sorting must be exactly per the Debian spec
No inclusion of external modules written to perform Debian packages sorting, as that would make it rather easy. Therefore golfing the above test program will not produce a legal answer, as it includes Debian::Dpkg::Version. You may of course look to the source of that module for inspiration if you lack imagination, but I believe there are shorter ways to do this.
You may assume that any input line whose format is invalid (i.e. does not constitute a version number conforming to the debian spec) must be retained, but may be sorted arbitrarily.
Equivalent version numbers may be sorted arbitrarily, e.g. 0.08-1 is equivalent to 0.8-1 as the numeric components 08 and 8 are compared as integers.
Save in respect of the arbitrary sort order of any lines not constituting version numbers conforming to the debian spec, and equivalent version numbers, your output should be identical to the test program above.
Ruby 2.0, 145 179 characters

puts$&lt;.sort_by{|a|(1..3).map{|i|"#{a[/^(\d+:)?(.+?)(-[^-]+)?
/,i]}".scan(/(\D*)(\d*)/).map{|w,n|w.bytes.map{|c|c&lt;126?c&gt;58?c:c+99:-1}+[0,n.hex]}}}


Correctly sorts both the linked reference input (though it generates a slightly different output order due to different sorting of equivalent version numbers, e.g. 1.06-2 vs 1.6-2) and the included test data.