とあるソフト会社の開発手法（コーディングスタイル）：第3話

【－ 目次 －】

第3話 「ソート」

いきなりですが「皆でしっかりチェック」した、文字列の配列（vector<string>）をソートをするコードを公開します。

#include        <vector>
#include        <string>

typedef std::vector<std::string> StringArray;

void swap(StringArray& array, int pos1, int pos2)
{
    if (pos1 == pos2)
        return;

    if (pos1 > pos2) {
        swap(array, pos2, pos1);
        return;
    }

    std::string str1 = array[pos1];
    std::string str2 = array[pos2];

    array.erase(array.begin() + pos2);
    array.erase(array.begin() + pos1);

    array.insert(array.begin() + pos1, str2);
    array.insert(array.begin() + pos2, str1);
}

int getMidValuePos(StringArray& array, int pos1, int pos2, int pos3)
{
    if (array[pos1] > array[pos2])
        swap(array, pos1, pos2);

    if (array[pos1] > array[pos3])
        swap(array, pos1, pos3);

    if (array[pos2] > array[pos3])
        swap(array, pos2, pos3);

    return pos2;
}

void sortBody(StringArray& array, int first, int last)
{
    if (first >= last)
        return;

    int pivot = getMidValuePos(array, first, (first + last)/2, last);

    int l = first;
    int r = last;

    while (l <= r) {
        while (array[l] < array[pivot])
            l++;
        while (array[r] > array[pivot])
            r--;

        swap(array, l, r);

        if (l < last)
            l++;
        if (r > first)
            r--;
    }

    sortBody(array, first, l - 1);
    sortBody(array, r + 1, last);
}

void sort(StringArray& array)
{
    sortBody(array, 0, array.size() - 1);
}

関数が4つほどありますが、その全てに突っ込みどころがある凄いコードです。

その１（配列内の値を入れ替える関数 swap）

配列から値を取り出して、その値を配列から削除して、場所を入れ替えて配列に挿入って……。
どんだけ無駄な事をしてるかと……。
vectorは、途中のデータを消したり、途中にデータを追加するのは苦手なのですよ？

普通に、値を交換したら良いじゃないですか。
値を入れ替える標準関数も用意されているわけですし。

std::swap(array[pos1], array[pos2]);

その２（配列内の3つの場所を指定して真ん中の値のものを返す関数 getMidValuePos）

真ん中の値を返すだけのはずなのに、何故か配列の中身を入れ替えています。
よく見ると、（真ん中を見つけるために）3つの要素だけでソートしてるんですよね。

並べ替えをしなくても、3回比較したら真ん中の値は求められますよ？

その３（配列の特定範囲をソートする関数 sortBody）

（最初と最後と中間の位置の値のうち、中間の値をピボットとして選択するという）クイックソートを効率的に動かす小技とか仕込む前に、やるべき事は沢山あると思うんだ。
例えば、ちゃんとソート出来るようにするとか、ちゃんとソート出来るようにするとか、ちゃんとソート出来るようにするとか。

って言うか、ソートできない時点で、既にソートする関数じゃないですよね。

その４（配列をソートする関数 sort）

そもそも、こんなの作らなくても

std::sort(array.begin(), array.end());

これだけで済むんだけど……。

【－ 目次 －】

今日の一冊
	逆転検死官 作者: 山崎 光夫 出版社/メーカー: 新潮社 発売日: 2003/02 メディア: 単行本

タグ：伝説のプログラマたち