|
User since: |
Apr 03, 2001 at 21:46 UTC
(24 years ago) |
Last here: |
Apr 18, 2016 at 21:54 UTC
(9 years ago) |
Experience: |
3497
|
Level: | Curate (13) |
Writeups: |
240
|
Location: | Minneapolis, MN |
User's localtime: |
Nov 09, 2024 at 18:53 -05
|
Scratchpad: |
View
|
For this user: | Search nodes |
|
As a general response to some sorting questions recently, here's the time reference table for various sorts:
Sort |
Worst Case |
Average Case |
Selection Sort |
N2 |
N2 |
Bubble Sort |
N2 |
N2 |
Insertion Sort |
N2 |
N2 |
Mergesort |
N*Log2N |
N*Log2N |
Quicksort |
N2 |
N*Log2N |
Radix Sort |
N |
N |
Tree Sort |
N2 |
N*Log2N |
Heap Sort |
N*Log2N |
N*Log2N |
Radix Sort Example from Wolf Book
#!/usr/bin/perl
sub radix_sort {
my $array = shift;
my $from = $array;
my $to;
# All lengths expected equal.
for ( my $i = length $array->[ 0 ] - 1; $i >= 0; $i-- ) {
# A new sorting bin.
$to = [ ];
foreach my $card ( @$from ) {
# Stability is essential, so we use push().
push @{ $to->[ ord( substr $card, $i ) ] }, $card;
}
# Concatenate the bins.
$from = [ map { @{ $_ || [ ] } } @$to ];
}
# Now copy the elements back into the original array.
@$array = @$from;
}
@array = qw(flow loop pool Wolf root sort tour);
radix_sort(\@array);
print "@array\n";
Commify Number, and set to 2 decimal places (Perl Cook + formatting)
Here's an explanation in perlfaq5.
sub commify {
local $_ = shift;
$_= sprintf("%.2f",$_);
1 while s/^([-+]?\d+)(\d{3})/$1,$2/;
return $_;
}
my XP Change Chart
|