On Nov 16, Pete Emerson said:
>Since we're on the topic of sorts, what are the arguments for
>the implemented quicksort vs. a radix sort?
(Perl now uses some mergesort hybrid.)
Ooh, radix sort. This is a cool technique, but it has a drawback: it
always runs in the same time. Sorting sorted data takes as long as
sorting UNsorted data. (Or sordid data!)
Here's a simple implementation of radix sort in Perl:
sub radix_sort {
my $a = shift;
for my $i (reverse(0 .. @$a-1)) {
my @table;
for (@$a) {
push @{ $table[substr $_, $i, 1] }, $_;
}
@$a = map @$_, @table;
}
}
The way this mechanism works is you sort the right-most character of all
the strings first, and then work your way towards the left-most.
V
bear
lion
arch
cake
V
cake
arch
lion
bear
V
arch
cake
lion
bear
V
cake
bear
lion
arch
arch
bear
cake
lion
--
Jeff "japhy" Pinyan [EMAIL PROTECTED] http://www.pobox.com/~japhy/
RPI Acacia brother #734 http://www.perlmonks.org/ http://www.cpan.org/
** Look for "Regular Expressions in Perl" published by Manning, in 2002 **
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
