バブルソート

C++でバブルソート - みずぴー日記 にインスパイヤされて バブルソート - Wikipedia を awk で実装してみます。 英語版の Wikipedia の Bubble sort - Wikipedia, the free encyclopedia にはいくつかの実装方法が掲載されていますが、ここでは最も簡単そうな実装を行います。

元々、バブルソートは安定なソートであることや実装が容易であることが特徴ですので、簡単な方法を使います。

#! /usr/local/bin/nawk -f
# bubble_sort.awk
# バブルソート
# usage: nawk -f bubble_sort.awk file

{
    line[NR] = $0;
}

END {
    bubble_sort(line, NR);

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

# ref: http://en.wikipedia.org/wiki/Bubble_sort
function bubble_sort(arr, num,    swapped, i, tmp) {
    do {
        swapped = 0;
        for (i = 1; i <= num - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = 1;
            }
        }
    } while (swapped)
}

ここに度々登場してくるマージソートに比べて実装が非常に簡単であることが分かると思います。

試すにあたって、seq 10 の結果を tac に渡したもの (つまり 10 からはじまって 1 で終わるもの) を渡してみます。

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

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