基礎が大事 - おっさんプログラマの戯れ言

基本・・・何より基本が大事！

以下の整数配列を昇順に並べ替えなさい。
int[] numbers = {8, 4, 3, 7, 6, 5, 2, 1};
①選択ソートで並べ替えるプログラムを作成しなさい。
②バブルソートで並べ替えるプログラムを作成しなさい。

言語はJavaで書いてみます。

【選択ソート】

public class Sort1 {
    public static void main(String[] args) {
        int[] numbers = {8, 4, 3, 7, 6, 5, 2, 1};

        for (int i = 0; numbers.length - 1 > i; ++ i) {
            int min = i;

            for (int j = i + 1; numbers.length > j; ++ j) {
                if (numbers[min] > numbers[j]) {
                    min = j;
                }
            }

            int temp = numbers[i];
            numbers[i] = numbers[min];
            numbers[min] = temp;
        }
		
        for (int i : numbers) {
            System.out.print(i);
            System.out.print(" ");
        }

        System.out.println();
    }
}

【バブルソート】

public class Sort2 {
    public static void main(String[] args) {
        int[] numbers = {8, 4, 3, 7, 6, 5, 2, 1};

        for (int i = 0; numbers.length - 1 > i; ++ i) {
            for (int j = 0; numbers.length - i > j + 1; ++ j) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
		
        for (int i : numbers) {
            System.out.print(i);
            System.out.print(" ");
        }

        System.out.println();
    }
}

【両者の違い】
選択ソートは、データ列中で一番小さい値を探し、1番目の要素と交換する。
バブルソートは、全ての要素に関して、隣接する要素と比較し、順序が逆であれば入れ替える。

両方とも計算時間はO(pow(n, 2))と低速なソートアルゴリズムである。
比較回数は一緒だが、交換回数は選択ソートの方が少ない。
ただし、バブルソートが安定ソートなのに対して、選択ソートは安定ソートではない。

詳しくはwikiで
http://ja.wikipedia.org/wiki/選択ソート
http://ja.wikipedia.org/wiki/バブルソート

【背景】
（以下、どうでも良く、まとまりのない、雑な話）
なぜこんなアルゴリズム入門的なことを急に思い立ったか。

言語やエディタやツールがどんどん賢くなっていく中、
プログラマの脳みそはどんどん退化していく。

私は最近、Objective-Cを使っていますが、それは本当に最近のことであって、
それまではずーーっとJavaばかり使っていました。
何かをソートしようと思ったら、Arrays.sortかCollections.sortを使ってきました。
実際、それですべて事足りていました。
（それ以前に、ソートはRDBMS側でやることが多い）

最近、C言語でデータをソートする機会がありました。
内容は詳しくは書きませんが、ある構造体へのポインタの配列を、
ある規則によって並べ替えるといったものでした。
データ構造の都合により、qsort関数を使えませんでした。
厳密には、データ構造を変更すればqsort関数を使えたのですが、
そこまでするほどのことでもなく、ソート速度もそこまで高速でなくて良い状況であったため、
これくらい自分で書けばいいや、ということで作り始めたわけですが・・・

そこで思ったのです。

「あれ？俺昔よりバカになってね？」

入社当初の、まだオブジェクト指向もJavaもWebプログラミングも知らなかったあの頃の私ならば、
タイプを止めることなくすらすらとC言語で簡単なソートくらいは書けたはずです。
あれから色々経験を積んできたはずなのに、今はなんだか、つっかえつっかえ、
「あれ？これでロジック合ってるのかな？」
なんて、デバッガなんて起動し始めて、なんともトロいこと。。。
危機感を覚えて、基本的なソートアルゴリズムを復習しましたとさ。

ビジネスプログラマの宿命なのか、はたまた私の脳みそが貧弱なのか、劣化が早いのか、

ともかく、

「たまには基礎的なアルゴリズムの学習（復習）をするのもいいよね」

と思った次第であります。。。

さもなければ、2ヶ月後に新入社員が入ってきたときに、

「あれ？先輩、バブルソートもできないんすか＾＾」

「そんなんで仕事やってけるなんて、この業界ちょろいっすね＾＾」

なんてことになってしまいかねない。

私の窓際の席とiMacが危うい。

ちなみに、
JavaのArrays.sortは改良クイックソート、
Collections.sortは改良マージソートだそうです。

http://docs.oracle.com/javase/jp/1.4/api/java/util/Arrays.html#sort(byte[])
http://docs.oracle.com/javase/jp/6/api/java/util/Collections.html#sort(java.util.List)

気が向いたらAPIのソース見てみようかと思います。