Bucket Sort & Distribution Counting Sort

Algorithm

まぁ、データの特性が利用できるならO(n log n)より速いアルゴリズムが存在するのは、その道の人には常識だったりもするが。

sub bucket_sort(\@&){
    my ($aref, $cref) = @_;
    my @bucket = ();
    $bucket[$_] = $_ for (@$aref);
    my $i = 0;
    defined $_ and $aref->[$i++] = $_ for (@bucket);
    return $aref;
}

うぇ、重複値があると要素が消失しちゃう。広義にはこういうのも bucket sort だけど、重複を許さないとかなりアプリケーションが限定されるような。弾さんも認識してて説明してないだけなんだろうけど。

sub bucket_sort {
    my ($array) = @_;
    my @bucket = ();
    for (@$array) {
        if (defined $bucket[$_]) {
            push @{$bucket[$_]}, $_;
        } else {
            $bucket[$_] = [$_];
        }
    }

    my @out;
    defined $_ and splice @out, @out, @$_, @$_ for @bucket;

    return \@out;
}

インターフェースが変わっているけど、こんな感じに bucket の要素を配列/リストにするのが多いんじゃないかなぁ。
自分は分布数えソート(Distribution Counting Sort)を使ったりする。こんなの。

sub dist_sort {
    my ($aref) = @_;
    my @count = ();

    $count[$_]++ for (@$aref);

    my $sum = 0;
    for my $i (0..@count-1) {
        my $t = $count[$i] || 0;
        $count[$i] = $sum;
        $sum += $t;
    }

    my @out;
    $out[$count[$_]++] = $_ for @$aref;
    return \@out;
}

一応簡単に手順解説。

  1. 対象配列を走査して各数値の出現回数を計数
  2. 出現回数から各 bucket の開始インデックスを確定
  3. 再度、対象配列を走査して対応する bucket に値を入れていく

ちなみに、Suffix Array を高速に構築するアルゴリズムなんかでは先頭の1、2文字をキーにソートするステップがあったりするんだが、そこではこれらのソートアルゴリズムが使われてたりする。
あと、文字列を対象とする場合は MSD Radix Sort (これも 内部では bucket sort も使うらしい) が速いとか、比較キーが複数ある場合(文字列ソート含む)は Multikey Quicksort が速いとかそういう話もあって非汎用ソートも結構奥が深い。