zmndgg
Last Updated: February 25, 2016
·
988
· gideon
5aefd3e85213e1c22ee31e4ce6123d40

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
Say Thanks
Respond

1 Response
Add your response

15601
5404ada11a0640e75e7ef5c3ac58472c

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

over 1 year ago ·