[1+1=2]

OneAndOneIs2

« The helpful thing about Linux..Git prompt: Tell me more »

Thu, May 16, 2013

[Icon][Icon]Quicksort golf

• Post categories: Omni, FOSS, Programming

I was going back over LYAH recently, and I came across the bit about Quicksort and how it's something of a poster child for Haskell because most other languages need 10+ lines of code to write it, whereas in Haskell you can do it in just a couple.

It didn't look like something that should need all that much code in Perl either, but a quick Google showed only some fairly enormous examples.

So I had a quick try, basically just re-writing the Haskell example into Perl. Which has no list comprehensions. But it does have map and grep, which accomplish much the same thing.

Here it is:

sub quicksort {
    my $array = shift;
    return [] unless (@$array);
    my $head = shift @$array;
    return [    @{ quicksort([grep { $_ <= $head } @$array])},
                $head,
                @{ quicksort([grep { $_ > $head } @$array])}
                ];  
    }   

And an example usage:

my $result = quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9];
$, = ',';print @$result,"\n";

$ ./qs.pl 
1,2,2,3,3,4,4,5,6,7,8,9,10,

So, four lines of perl. You could get it down to three if you just used $_[0] instead of assigning it to $array, but I suppose some might say that the greps should be counted as a line of code each. Still only half a dozen lines tho.

I don't see what all the fuss is about :)


5 comments

Chankey Pathak
Comment from: Chankey Pathak [Visitor]
Good one. Perl is beautiful. I rember writing quicksort program in C and that went too big.
16/05/13 @ 17:43
pdh
Comment from: pdh [Visitor]
one line
sort @array
:p
16/05/13 @ 20:14
oneandoneis2
Comment from: oneandoneis2 [Member] · http://geekblog.oneandoneis2.org/
Misses the point a bit :P
16/05/13 @ 20:23
Francis
Comment from: Francis [Visitor]
golf, you say?

sub quicksort {
@_ and return (
quicksort (grep { $_ < $_[0] } @_),
grep ({ $_ == $_[0] } @_),
quicksort (grep { $_ > $_[0] } @_)
);
();
}


I suppose that's technically at least four lines.
17/05/13 @ 00:39
oneandoneis2
Comment from: oneandoneis2 [Member] · http://geekblog.oneandoneis2.org/
heh :) Nice
17/05/13 @ 08:41
 

[Links][icon] My links

[Icon][Icon]About Me

[Icon][Icon]About this blog

[Icon][Icon]My /. profile

[Icon][Icon]My Wishlist

[Icon]MyCommerce

[FSF Associate Member]


March 2017
Mon Tue Wed Thu Fri Sat Sun
 << <   > >>
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Search

User tools

XML Feeds

eXTReMe Tracker

Valid XHTML 1.0 Transitional

Valid CSS!

[Valid RSS feed]

blogging tool