Excel 順にソート

Excel順ソート - みずぴー日記 にインスパイヤされて awk を使ったマージソートで記述してみます。

gawk には asort() 関数が実装されており、通常のソートであれば高速かつ簡単に awk で実装できるようになっていますが、ソートの条件を指定することができないため、複雑な条件でのソートは自前で用意する必要があります。

既に AWK Users JP :: 平均値順にソート などで複雑な条件を使ったソートを記述していますので、ここでは同様にマージソートを用いて実装してみます。

以下のプログラムの中でもコメントしてありますが、再帰マージソートのコアとなる比較の部分を修正することで実装することができます。

#! /usr/bin/gawk -f
# merge_sort.awk

BEGIN {
    arr[1] = "a";
    arr[2] = "b";
    arr[3] = "aa";
    arr[4] = "zz";
    arr[5] = "c";

    # 配列の数を数える。gawk では length() 関数を利用できる
    # num_arr = length(arr);
    for (i in arr) {
        num_arr++;
    }

    merge_sort(arr, 1, 5);

    for (i = 1; i <= 5; i++) {
        print arr[i];
    }
}

# function for recursive merge sort
function merge_sort(arr, a, b, key,   k) {
    if (a < b) {
        k = int((a + b) / 2);

        merge_sort(arr, a, k, key);

        merge_sort(arr, k + 1, b, key);

        merge(arr, a, k, b, key);
    }
}

# function for merge
function merge(arr, a, k, b, key,   i, j, p, c) {
    j = i = a;
    p = k + 1;

    while (a <= k && p <= b) {
        # 文字列の長さが同じ場合には通常の比較
        if (length(arr[a]) == length(arr[p])) {
            if (arr[a] <= arr[p]) {
                c[i++] = arr[a++];
            } else {
                c[i++] = arr[p++];
            }
        # 文字列の長さが異なる場合には短いほうが優先
        } else {
            if (length(arr[a]) < length(arr[p])) {
                c[i++] = arr[a++];
            } else {
                c[i++] = arr[p++];
            }
        }
    }

    while (a <= k) {
        c[i++] = arr[a++];
    }

    while (p <= b) {
        c[i++] = arr[p++];
    }

    while (j <= b) {
        arr[j] = c[j];
        j++;
    }
}

つまり、文字列の長さをソートの条件のひとつとして加えていることになります。

それでは実行してみます。

$ gawk -f merge_sort.awk
a
b
c
aa
zz

確かに awk でソートを行うのは少々難しいのですし、こうした特定の条件ごとにプログラムを書き換えることは望ましくないのですが、アルゴリズムの内容とコードとの対比ができれば自由に組み替えることができます。

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