Sorting Techniques

Introduction

Sorting is a commonly needed operation in all kinds of programs. Luckily, for us perl programmers, perl provides a very simple yet extremely powerful mechanism to accomplish any sort you might think of. This article is about teaching the novice programmer how to sort lists of things, while showing to the more experienced folks certain techniques and ideas that could be new to them if they are migrating from a different language.

Moving to the meat of the matter staight away, we'll start from talking about comparison. Obviously, in order to put a list of things in order, you'll have to first define that order. Order is defined by how things compare to each other. If I give you two items from the list, can you tell me which one is bigger / better / nicer / sexier ... [insert you favourite adjective here] than the other? Or tell me thet they are both of equal order? Well, that's just about it! If you give me a list of items and promise me that you can answer this question for any pair of them, I can make a sorted list of them. All I have to do is take all possible pairs and ask you "how do these two compare?" and arrange them accordingly to finally come up with a sorted list. Actually there are even smarter ways to do it, minimising the amount of comparisons needed, but that is not an issue here, as we will see soon that perl performs that task for us, and we trust perl that it uses the least expensive method.

Now, the issue in question being comparison, I assume you must be familiar with all (or at least most) of perl's comparison operators. There's a list of them:

Numbers	Strings
<	lt
>	gt
<=	le
>=	gr
==	eq
<=>	cmp

Now the first five rows should be ok, they're just like math. But what are the <=> and cmp operators? Basically, the expression $a <=> $b (or $a cmp $b for strings) returns one of the values 1, 0, -1 if $a is, respectively, larger, equal or lower than $b. (see table below)

Relation of $a and $b	Value Returned by $a <=>
$a greater than $b	1
$a equal to $b	0
$a less than $b	-1

Does that ring a bell? Coming to think of it, the <=> and cmp operators actually provide the answer to the question we were investigating earlier when we talked about how to sort by using a comparative criterion. So, if we already have an operator that answers this question ("how do two items compare?") all we need is a function that will take a list of items and perform the necessary comparisons to arrive at a sorted list. And guess what? That's exactly what perl's sort operator does. So, if you have an unsorted list @not_sorted and want to created a sorted list @sorted, you just say:

@sorted = sort { $a <=> $b } @not_sorted # numerical sort or @sorted = sort { $a cmp $b } @not_sorted # ASCII-betical sort or better @sorted = sort { lc($a) cmp lc($b) } @not_sorted # alphabetical sort

Looking at the sort function, we notice that it is exactly as we described it in words, earlier in this article. Perl needs just two things: the list of items to sort, and a subroutine that answers the question "how do these two compare?" for any pair of items in the list. Perl puts the two items it want to compare int the special variables $a and $b and your function is responsible to give a return value that corresponds to the existing relationship of the two, as shown in the table shown earlier.

Here, in this simple example, we used perl's built-in comparison operators that work for numerical and alphabetical (not realy... to be correct it is ASCII order) sorting. Of course, you can roll your own comparison function to create sorts for any kind of ordering you wish to have. Before you start coding your own functions, take a look to the following examples:

Get a list of hash keys sorted by value.

@sorted = sort { $hash{$a} cmp $hash{$b} } keys %hash;

Get a reverse sort of a list.

@sorted = sort { $b cmp $a } @list; Which can also be done with @sorted = reverse sort { $a cmp $b } @list;

Get an alphabetical sort of words, but make 'aardvark' always come last.

(Now, why you would want to do that is another question...)

@sorted = sort { 
  if ($a eq 'aardvark') { return 1; }
  elsif ($b eq 'aardvark') { return -1; }
  else { return $a cmp $b; } 
} @words;

Save This Page

Comments


Dr Vee	Posted at 5:39pm on Thursday, March 8th, 2007
Googled over a dozen of other pages, nothing comes close to this. THANKS ALOT!
sakthi	Posted at 1:52am on Tuesday, March 13th, 2007
how to sort the the array of items which contains list of file names. these can distinguished by date
dre	Posted at 2:18pm on Friday, March 23rd, 2007
yahooed one page, and this was it, i did not have to google 20 pages.
amsanjeev	Posted at 12:34am on Saturday, March 31st, 2007
simple and to the point article . Thanks a lot.
Todd	Posted at 1:34pm on Sunday, April 1st, 2007
Wonderful article, helped a lot.
willtriv	Posted at 7:02am on Thursday, April 5th, 2007
reverse sorting was made very clear after seeing this example :)
Prabhu	Posted at 3:07pm on Thursday, April 5th, 2007
sakthi, I had an array like this: $fileNames[0] = logfile200704050000 $fileNames[1] = logfile200704050050 $fileNames[2] = logfile200704050812 $fileNames[3] = logfile200704050225 and sorted them like this: @sorted = sort { substr($a,8,12) substr($b,8,12) } @fileNames;
Prabhu	Posted at 3:10pm on Thursday, April 5th, 2007
The website took out the operator on the last line. It should look like this without the spaces on either side of the '=' @sorted = sort { substr($a,8,12) < = > substr($b,8,12) } @fileNames;
Stan	Posted at 1:33am on Wednesday, April 18th, 2007
Great page, very useful! Simplified some pretty tricky problems I was having.
Randal L. Schwartz	Posted at 4:52am on Thursday, April 19th, 2007
I have plenty of examples of using Perl's sort (including the now-famous "Schwartzian Transform", named after me, but not BY me) at my 250-magazine articles available on my website. Use a google search of "sort site:stonehenge.com" (but without the quotes) and have fun reading.
Dan	Posted at 2:07am on Friday, April 27th, 2007
How do you sort for example chapters in a book? They go like 1, 1.1, 1.1.1, 1.1.2, 1.2, 1.3, 2, 2.1, etc... Numeric sort just won't put it in that order.
Al	Posted at 7:15am on Friday, June 15th, 2007
Depending on how deep the book is, you could strip the .'s, then pad right with 0's so all values are 4 digits long. e.g: 1000 (was 1) 1100 (was 1.1) 1120 (was 1.1.2) 1200 etc 1300 2000 2100 So you need to strip the ".", then pad. Look for replace and sprintf.
Milind	Posted at 8:34am on Friday, July 13th, 2007
Awesome article. Poured over ton of sites, and this article is like the most concise, to the point article. Read first 8 lines, implemented my sort function inline and I was good to go. You should bill my company!
Chris	Posted at 2:54am on Wednesday, July 18th, 2007
schweeeeeeeeeeeeet!!!!!!!!!!!!
Anonymous	Posted at 11:18am on Wednesday, July 18th, 2007
good job, also would be nice to add a paragraph about how the interpreter compares the strings. for example baaaaaa> azzzzzzz
mcb	Posted at 1:54pm on Wednesday, July 25th, 2007
If you have a list of hash refs and you want to sort by two values (for example, sort primarily by people's ages, but if the ages are the same, sort alphabetically), do something like this: @sorted = sort { ($a->{age} $b->{age}) \|\| ($a->{name} cmp $b->{name}) } @not_sorted;
Willem Kernkamp	Posted at 8:46am on Monday, July 30th, 2007
To the point and concise! Thanks a lot.
Paul	Posted at 1:44am on Thursday, August 9th, 2007
"Get an alphabetical sort of words, but make 'aardvark' always come last. (Now, why you would want to do that is another question...) " This was exactly what I needed, thanks very much!
Daniel	Posted at 12:14am on Wednesday, August 15th, 2007
You can also sort a hash of hashes (or hash of arrays or whatever) based on values in any subscript as such: sort { $not_sorted{$a}{name} cmp $not_sorted{$b}{name} } keys %$not_sorted; ... useful where you might have multiple properties for each element, as it allows you to sort on any given property. Can of course be combined with mcb's method for sorting on multiple criteria.
Daniel	Posted at 12:15am on Wednesday, August 15th, 2007
typo in the above, should be: sort { $not_sorted{$a}{name} cmp $not_sorted{$b}{name} } keys %not_sorted;
oscii	Posted at 11:46pm on Wednesday, August 15th, 2007
thank you! teh 1 minute bugfix before the release ;)
David	Posted at 4:57am on Friday, August 17th, 2007
This is one kind of sort you did not talk about. You want to sort the following: Die Hard, Die Hard 2, Die Hard 3. The sort function will put Die Hard last. I do not want to add a 1 for Die hard. How would you make a sort to fix this problem? Thanks
David	Posted at 4:27am on Tuesday, August 21st, 2007
So clear and so helpful! Thanks!
Daniel	Posted at 7:44pm on Wednesday, August 22nd, 2007
There appears to be a mistake in the last section of the article (making 'aardvark' always come last). I've recently had to use something similar to this, and the way it's written here will actually force 'aardvark' to always come _first_, not last. Reverse the return values (-1, 1) to correct this.
perlfect	Posted at 7:28am on Thursday, August 23rd, 2007
@Daniel: Thanks for spotting that. I have updated the article above.
Nubee	Posted at 4:13pm on Wednesday, August 29th, 2007
How can I sort a sub-array based on the order another array?
David	Posted at 7:39am on Tuesday, September 4th, 2007
My application requires sorting of a large hash (> 100,000,000), but I am only interested in the largest 50,000 entries. Is there an economical way to first get the largest 50,000 entries (all floats) and then sort only those rather than sorting the whole hash?
Pacman	Posted at 11:35pm on Tuesday, October 2nd, 2007
To decide to which are the largest 50000 entry you need to short the whole thing first.
Martin	Posted at 7:12am on Tuesday, October 9th, 2007
David, the most efficient algorithm to find the largest i elements out of n elements works in expected linear time O(n) (as opposed to at least O(n log n) for sorting). Pacman is wrong. The algorithm is similar to quick sort, partitioning the array repeatedly but always making just one recursive call to the half where the split should occur (in your case where the position 50000) is. You should check out the Intro to Algorithms book or find information on Selection (order statistics) on the web somewhere to get details. This procedure is significantly faster especially when you deal with such a huge array of 100 mil. elements.
Sujeet	Posted at 1:20am on Wednesday, October 17th, 2007
How Sort numeric array or Character array without using sort function in Perl
gpm1982	Posted at 12:51am on Friday, October 26th, 2007
"Get an alphabetical sort of words, but make 'aardvark' always come last. (Now, why you would want to do that is another question...) " Seriously, this helped me a lot for my taks. Thanks a lot
Brenda	Posted at 7:03am on Tuesday, October 30th, 2007
So how do I get the sort to ignore the case of the characters?
Brenda	Posted at 4:45am on Friday, November 2nd, 2007
Continuing on from the the previous comment I used @sorted = sort { lc $hash{$a} cmp lc $hash{$b} } keys %hash; to sort with upper and lower cases mixed and it does not work.
Perlfect	Posted at 6:53am on Friday, November 2nd, 2007
@Brenda: Is your intention to sort the values of the hash according to its keys in a case insensitive way? Perhaps what you intended to do is: @sorted = sort { lc $a cmp lc $b } keys %hash; which will give you the keys of the hash sorted as you desire.
TJ	Posted at 10:37am on Thursday, November 29th, 2007
MCB - your comment really helped...thanks a TON
Sneha	Posted at 11:19pm on Tuesday, January 15th, 2008
when sorting the list the words in uppercase are given highest priority than words in lowercase. why is it so???
John W. Krahn	Posted at 5:57pm on Wednesday, January 16th, 2008
Your table of comparison operators has one error and one omission. >= gr That should be: >= ge And you are missing: != ne HTH.
jhon	Posted at 5:47am on Monday, January 21st, 2008
cool!!!!!!!
Mark T	Posted at 3:14am on Thursday, January 31st, 2008
When sorting words and digits, do the words always appear first?
Matt	Posted at 6:43am on Thursday, January 31st, 2008
I am trying to sort on a value within a hash of hashes. 'Trade' is the key to the value which is a number. Pls can anyone advise on the syntax? The key is at the following level: %tradeSummary{top25}{Trade} foreach my $instrument( sort{$tradeSummary{top25}{Trade}{$a}$tradeSummary{top25}{$instrument}{Trade}{$b}} keys %{$tradeSummary{top25}} ){
Matt	Posted at 7:36am on Thursday, January 31st, 2008
I've managed to resolve this referencing issue. The Trade value actually belonged in the first item of an array, so the following worked: foreach my $instrument (sort {$tradeSummary{top25}{$b}[0]$tradeSummary{top25}{$a}[0]} keys %{$tradeSummary{top25}} ){
Andre	Posted at 9:41pm on Thursday, February 21st, 2008
Fantastic article! Helped me in my Perl/CGI programming course.
Gaborik	Posted at 7:53pm on Thursday, March 6th, 2008
Very nice article. Helped me a lot.
Anupam Nandan	Posted at 4:47am on Wednesday, March 19th, 2008
gud work ..
almitra	Posted at 11:14am on Friday, March 28th, 2008
I want to sort a file where the starting is the file name followed by the sequence , how do i sort these two >ugast 1234.... agtctgsft > ecoli12k12 gcttctag I just want the sequence and not the line staring with >
et	Posted at 4:59am on Tuesday, April 22nd, 2008
how about random order: sort { int(rand(3))-1 } @table
Thor Is my Real Name and I'm not Swedish	Posted at 11:40am on Friday, April 25th, 2008
THANK YOU WRITER OF THIS POST
Anonymous	Posted at 8:48am on Tuesday, April 29th, 2008
I am new to perl how can we do sorting in hash value - currently using following code for (my $i = 0 ; $i< $#docs ; $i++) { for (my $j = 0 ; $j< $#docs-$i ; $j++) { if( $docs[$j]->{"LAST_MODIFIED"} > $docs[($j+1)]->{"LAST_MODIFIED"} ) { my $temp = $docs[$j+1]; @docs[$j+1] =$docs[$j] ; @docs[$j] = $temp; } } } thanks

Comments to date: 48.

Like it? Share it!

Post to
del.icio.us

Hosted Perlfect Search^(beta)
Don't have the time or the expertise to install and maintain Perlfect Search? Then our freehosted Pelrfect Search service is for you!

The Regex Tutor

Try your regular expressions online with the regex tutor.