PGTS PGTS Pty. Ltd.   ACN: 007 008 568

point Site Navigation

point Other Blog Threads



  Valid HTML 4.01 Transitional

   Give Windows The Boot!
   And Say Goodbye To Viruses!

   Ubuntu

   If you own a netbook/laptop~
   Download Ubuntu Netbook!






PGTS High and Mighty Blog

Thread: Perl Programming

GP JPG
Gerry Patterson, The man who almost invented humble sarcasm tags(Invisible to non-sarcastic browsers)

Using The Sort Pragma With Perl 5.8


Chronogical Blog Entries:



Date: Tue, 27 May 2008 19:37:46 +1000

A few years ago, while using the perl sort() routine, I came across the problem of preserving sort order. The problem often arises when you wish to preserve the original order of a list while using quicksort. The algorithm generally used by quicksort, is a binary-tree method that will exchange array items. And so, if the list contains non-unique sort keys the original order may not be preserved.

Early versions of perl (5.6 and earlier) used quicksort, and exhibited this behaviour. At the time I resolved the problem by writing a C program which called the library quicksort, qsort(). By providing my own comparison procedure I was able to compare the address of the elements when the keys were equal, and thus preserve the original order.

Since version 5.8 of perl, mergesort is the preferred algorithm. This algorithm was popular for tape and disk based methods of sorting. For a random list it may not work as quickly as quicksort. However it does preserve the original order. Also in version 5.8 you can use the sort pragma to specify how the sort behaves. If it is important to preserve the natural order, this can be done with:

	use sort 'stable';

You can read about this in the perl man pages by entering "perldoc sort" or "man 3 sort" at the command line. Perl version 5.8 also gives the option of specifying the sort algorithm with one of these commands:

	use sort '_mergesort';
	use sort '_qsort';

The _quicksort qualifier can be used as alternative for _qsort. It even seems that 5.8 has made it possible to have a stable quicksort, using this:

	use sort qw(_qsort stable);

Although the 5.8 man page does warn that future versions of perl may ignore the _qsort and _mergesort qualifiers. (which seems to imply that the stable qualifier will continue to be supported).


Other Blog Posts In This Thread:

Copyright     2008, Gerry Patterson. All Rights Reserved.