Quicksort in Perl

I have been learning Perl over my winter break for a job that I will be starting this semester. My main source has been Impatient Perl, a free book targeting programmers that need to quickly pick up Perl. About halfway through reading it I realized that I was doing a minimal amount of coding and, consequently, stuff probably was not sticking. So I decided to write a quicksort subroutine. Sadly, I am writing this post the morning after doing this. Next time I will be sure to blog as I go.

About Quicksort

First, a little bit about Quicksort (all of this info and the picture can be found on Wikipedia's article on Quicksort). Say you are sorting a list of numbers by hand; if you wanted to use Quicksort to do this, here are the steps that you would follow:

1. If you only have one number in your list, you are done, so return it.
2. Othenrwise, choose one number from your list and call it the "pivot". There are a couple ways that you could choose the pivot, but it is simpliest to just pick the first number.
3. Go through the remaining numbers and put them into two groups: one group of numbers less than or equal to the pivot (call this group "smalls"), the other group ("larges") with the rest.
4. Quicksort each group.
5. Stick the now-sorted smalls and larges together with the pivot between them in whatever order you would like to sort the numbers. For ascending order you would return [smalls,pivot,larges]; descending [larges,pivot,smalls].

Quicksort is a divide and conquer sorting algorithm. This means that whatever is being sorted is divided into two groups with themselves are then sorted. This gives Quicksort and average running time of O(n*lg(n)) (the list is divided lg(n) times and each time you divide you go through all n of the elements in linear time). So now let us see about implementing this in Perl.

My Implementation

sub quick_sort {
  # quick_sort - given an array, return a copy of that array sorted 
  #              in ascending order

  # Step 1. base case - list is empty
  if (!@_) {
    return;
  }
  # Step 2. take first element as pivot
  my $pivot = pop(@_);
  # Step 3. divide the rest of the list into two groups
  my (@smalls, @larges);
  foreach (@_) {
    ($_ <= $pivot) ? push(@smalls, $_) : push(@larges, $_);
  }
  # Step 4. Quicksort the two groups
  @larges = quick_sort(@larges);
  @smalls = quick_sort(@smalls);
  # Step 5. Stick the pivot at the front of larges and stick that at
  #         the end of smalls, returning the list 
  #         [smalls, pivot, larges]
  unshift(@larges, $pivot);
  push(@smalls, @larges);
  return @smalls;
}
# test snippet
my @ex;
foreach (0 .. 10) {
  $ex[$_] = int(rand(100));
}
print "unsorted: @ex\n";
@ex = quick_sort(@ex);
print "sorted: @ex\n";

Running this produces the following output:

unsorted: 14 31 36 38 24 31 68 85 90 80 26
sorted: 14 24 26 31 31 36 38 68 80 85 90

It works. It could be changed such that it sorts the given array in place, but I prefer to keep my code functional whenever I can (and it would be more complicated to do it the the other way).

A Better Way

Considering this is the first "real" piece of code I have written in Perl, I am certain that there is a better, less verbose way of getting this done. I did a bit of looking around and I found the simpliest and cleanest solution at Rosetta Code:

sub quick_sort {
    my @a = @_;
    return @a if @a < 2;
    my $p = pop @a;
    quick_sort(grep $_ < $p, @a), $p, quick_sort(grep $_ >= $p, @a);
}

This is much shorter than my implementation. It uses the function grep, which is named for and behaves like Unix's grep. Given a code block or a regex and a list, it evaluates the block or the regex, returning the list of elements for which the expression evaluated true. Those familiar with lispy functions can think of this as a filter function.

Wrapping Up

Not much to say here. This was just a simple exercise and I have a way to go before I am
fluent in Perl. Feel free to comment if you have anything to add or discuss.