バケットソート (Bucket Sort)

404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速い にインスパイヤされて、バケットソートを awk で作ってみます。

バケットソート - Wikipedia にアルゴリズムが出ていますが、「比較をしないソート」というのが最大のポイントになります。

ただし、各配列を入れるバケツ (配列 bucket) が要素の数だけ必要になるためメモリがそれなりに必要になりますし、ここでは有限な整数であることを元に作成します。

#! /usr/local/bin/nawk -f
## bucket_sort.awk
## バケットソート

{
    line[NR] = $0;
}

END {
    bucketsort(line, NR);

    for (i = 1; i <= NR; i++) {
        print line[i];
    }
}

## bucketsort():    バケットソート (Bucket Sort)
##  in:     配列 arr
##          配列数 n
##  out:    ソートされた配列 arr
function bucketsort(arr, n,   i, j) {
    j = 1;

    for (i = 1; i <= n; i++) {
        if (bucket[arr[i]] == "") {
            bucket[arr[i]] = arr[i];
        } else {
            count[arr[i]]++;
        }
    }

    for (i = 1; i <= n; i++) {
        if (bucket[i] == "") {
            continue;
        }
        for (k = 1; k <= count[i] + 1; k++) {
            arr[j++] = bucket[i];
        }
    }
}

どこでも比較していないのがポイントです。

実行してみましょう。

$ seq 10 | tac | gawk -f bucket_sort.awk
1
2
3
4
5
6
7
8
9
10

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png