http://www.perlmonks.org?node_id=69394

User since: Apr 03, 2001 at 21:46 UTC (23 years ago) Last here: Apr 18, 2016 at 21:54 UTC (8 years ago) Experience: 3497 Level: Curate (13) Writeups: 240 Location: Minneapolis, MN User's localtime: Nov 28, 2023 at 14:59 -05 Scratchpad: View For this user: Search nodes

Nodes I'm Proud of
The Drama of being a developer
The Drama of being a developer II
The Drama of being a developer III
The Drama of being a developer IV
Developer Accountability
Crypto Discussion
Crypto Discusion II
My Jet Direct Printer control code
My (Humor) The IT Secret Service
My First Tutorial

Misc
My 'Blog
My Use.Perl.org Journal
God Bless the Onion
Wanna learn more about Improv?
Dictionary of Algorithms, Data Structures, and Problems
Angst Technology Comic Strip
Sinfest Comic Strip
Fuzzy Logic Comic Strip
HTML Converters

Book List
Code Complete by Steven McConnell

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";
[download]

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 $_;
}
[download]

my XP Change Chart