挿入ソート

Insersion Sort - みずぴー日記 にインスパイヤされて、ここは awk らしく instertion sort (挿入ソート) を作ってみます。

挿入ソート は、以下のような特徴があります。

  • O(n^2) の計算である
  • 安定なソートである

様々なところで挿入ソートの awk による実装があると思いますが、以下のようなものが一般的でしょう。

#! /usr/local\bin/nawk -f
# insert_sort.awk
# 挿入ソートを行います。
# usage: nawk -f insert_xort.awk foo.txt

{
    line[NR] = $0;
}

END {
    insert_sort(line);

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

# insert_sort:  挿入ソートを行います
#   in:     配列 (arr)
function insert_sort(arr,    i, j, num, tmp) {
    for (i in arr) {
        num++;
    }

    for (i = 2; i <= num; i++) {
        for (j = i; j > 1 && arr[j - 1] > arr[j]; j--) {
            tmp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = tmp;
        }
    }
}

実行してみます。

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

時間的なものを計測してみましょう。

$ time seq 1 | tac | gawk -f insert_sort.awk
seq 1  0.00s user 0.00s system 0% cpu 0.002 total
tac  0.00s user 0.01s system 494% cpu 0.002 total
gawk -f insert_sort.awk  0.00s user 0.00s system 0% cpu 0.002 total

$ time seq 10 | tac | gawk -f insert_sort.awk
seq 10  0.00s user 0.00s system 0% cpu 0.008 total
tac  0.00s user 0.00s system 0% cpu 0.009 total
gawk -f insert_sort.awk  0.00s user 0.00s system 0% cpu 0.008 total

$ time seq 100 | tac | gawk -f insert_sort.awk
seq 100  0.00s user 0.01s system 109% cpu 0.009 total
tac  0.00s user 0.00s system 0% cpu 0.009 total
gawk -f insert_sort.awk  0.02s user 0.00s system 93% cpu 0.021 total

$ time seq 1000 | tac | gawk -f insert_sort.awk
seq 1000  0.00s user 0.00s system 0% cpu 0.003 total
tac  0.00s user 0.00s system 0% cpu 0.003 total
gawk -f insert_sort.awk  0.92s user 0.01s system 100% cpu 0.929 total

$ time seq 10000 | tac | gawk -f insert_sort.awk
seq 10000  0.01s user 0.00s system 84% cpu 0.012 total
tac  0.01s user 0.00s system 46% cpu 0.022 total
gawk -f insert_sort.awk  77.73s user 0.14s system 99% cpu 1:17.91 total

1000 までは 1 秒以内ですが、10000 になったとたんに 77 秒もかかっていることが分かります。

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