zmndgg
Last Updated: February 25, 2016
·
1.025K
· gideon

An elegant Perl quick sort with inspiration from Haskell

So If you've read my earlier article I'm all for learning many things and drawing inspiration from many places.

I've been learning me a haskell, and I came to this part of the book where there is a slick haskell quick sort implementation.

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted  

Notice how the implementation is literally telling you what it's doing.

> If I get an empty list return an empty list
> if I have a list
 >>> take the first element. 
      | get items smaller than first element THEN sort these
      | get items larger than first element   THEN sort these
      | return 
           sorted smaller items + first element + sorted larger items 

I wanted to capture the same idea and feeling in perl, and so I did, this is what it looks like:

Ok, I have no idea why @xs renders weird here. See code as gist here.

sub sort_
{
    my @xs = @_;
    if(scalar(@xs) == 0) {return ();}
    my @lesser = sort_(grep { $_ <  $xs[0]  } @xs );
    my @greater = sort_(grep { $_ > $xs[0]  } @xs );
    return (@lesser, $xs[0], @greater);
}

Usage:

my @items = (101, 1,90,10,4,2,100);
say join ",", sort_ @items; # 1,2,4,10,90,100,101

1 Response
Add your response

15601

A similar self explanatory implentation in Perl:
sub sort_ {
@_ and return (
sort_ (grep { $_ < $[0] } @),
grep ({ $_ == $[0] } @),
sort_ (grep { $_ > $[0] } @)
);
();
}

over 1 year ago ·