平均値順にソート

平均値順にソート - みずぴー日記 にインスパイヤされて平均値順にソートしてみます。 平均値順にソート - みずぴー日記 に書かれている Perl スクリプトを見れば分かりますが、Perl に実装されている sort 関数の柔軟性の高さに awker としては嫉妬してしまいます。

問題は以下のようなものです。

  • 複数の整数を平均値に近い順にソートするプログラムを作成せよ。平均値は切り捨てして整数値で、平均値との距離が等しい場合は値の小さな方を優先するものとする。

つまり、以下のようなソートプログラムを組めば良いことになります。

  • 平均値からの差が同じ場合には値が小さい方を優先
  • 平均値からの距離が異なる場合には近い方を優先

今までに何度も紹介しているマージソートが比較的分かりやすかったので、マージソートで実装してみます。

#! /usr/local/bin/nawk -f
# sort_by_avg.awk
# 平均値順にソート
# usage: nawk -f sort_by_avg.awk

BEGIN {
    str = "4 2 1 3";
    num = split(str, arr);

    # Merge Sort
    merge_sort(arr, 1, num);

    # ソートされた配列の表示
    for (i = 1; i <= num; 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 (abs(arr[a] - avg(arr)) == abs(arr[p] - avg(arr))) {
            if (arr[a] <= arr[p]) {
                c[i++] = arr[a++];
            } else {
                c[i++] = arr[p++];
            }
        # 平均値からの距離が異なる場合には近い方を優先
        # つまり、ソート対象が異なる
        } else {
            if (abs(arr[a] - avg(arr)) < abs(arr[p] - avg(arr))) {
                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++;
    }
}

# avg():    配列の平均値を求める
#   in:     配列 arr
#   out:    配列 arr の平均値
function avg(arr,    i, sum, num) {
    for (i in arr) {
        sum = sum + arr[i];
        num++;
    }

    return sum / num;
}

# abs():    絶対値を求める
#   in:     数値 num
#   out:    数値 num の絶対値
function abs(num) {
    return (num > 0) ? num : -num;
}

コードとしては長くなってしまいましたが、マージソート自身がどこで比較を行い、どこで値を入れ替えているかが分かっていれば、難しくはありません。 早速実行してみましょう。

$ nawk -f sort_by_avg.awk
2
3
1
4

この例はソートを理解する上でも面白く、各言語のソートの実装の柔軟性を見る上でも面白かったので解いてみました。

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