The Beauty of a Perl Quicksort

By pid on

Yet Another Misleading Title. :)

err...I have to say, (I can't remember the exact time I met this version of quicksort), ever since the Haskell version was born, there were (and still are) various implementations available in various languages. This version of quicksort is a very nature "translation" of what the algorithm is:

function quicksort(list) {
    select a pivot;
    return (quicksort([x|x<pivot]), pivot, quicksort([x|x>pivot]));
}

Today, I met this version again in here (reddit.com). For convenience, let me repost the Lisp code:

(defun quicksort (lis) (if (null lis) nil
  (let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (< a x))))
    (append (quicksort (remove-if-not fn r)) (list x)
      (quicksort (remove-if fn r))))))

I wonder if I could reinvent(port, steal, rob, grab...whatever) it to Perl...and this is what I did:

sub quicksort {
    return () if @_ == 0;


    my ($head, @tail) = @_;

    my $less_than_head = sub { $_[0] < $head };



    return quicksort( grep {   $less_than_head->($_)   }  @tail ), 

           $head,

           quicksort( grep { not $less_than_head->($_) }  @tail );

}

...and Rosetta Code can always bring me a "better(more Perlish)" one:

sub quicksort {
	@_ <= 1 ? @_ : do {
		my $pivot = pop;
		quicksort( grep {$_ <= $pivot} @_ ), 
		$pivot, 
		quicksort( grep {$_ >  $pivot} @_ )
	}
}

Don't you think my Perl code is "beautiful"(and more like plain English) too?

IMHO, the beauty comes out of the way it is implemented, not the language we use. "Perl is ugly, I want you to create beautiful things in Perl", we all agree with that. ;-)

Tagged as:

, ,

1 Comment

Author Profile Page Aristotle | February 3, 2011 1:28 PM | Reply

Comparing an array with 0 is less idiomatic than just using it as a boolean. And to me that closure only makes the code more Java-ishly verbose: I read “$_ < $head” as “it’s less than head” in my head anyway, and spelling that out thrice does nothing more than make it less concise.

So I’d consider this version even straighter, and even nicer:

sub quicksort {
    return if not @_;
    my ( $head, @tail ) = @_;
    return (
      quicksort( grep { $_ <  $head }  @tail ), 
      $head,
      quicksort( grep { $_ >= $head }  @tail ),
    );
}

But in fact I would write it like so:

sub quicksort {
    return if not @_;
    my $pivot = shift @_;
    return (
      quicksort( grep { $_ <  $pivot }  @_ ), 
      $pivot,
      quicksort( grep { $_ >= $pivot }  @_ ),
    );
}

That makes it problem domain language (“pivot”) rather than solution domain mumbo jumbo (“head”, “tail”). (I understand the mumbo jumbo and use it where appropriate, mind you.) It happens to be more efficient too.

Leave a comment

About pid

user-pic I blog about Perl.

More info »