ソート処理時間、選ぶアルゴリズムでこんな差が！：いまから始めるアルゴリズム（2）（1/2 ページ）

プログラミングの基礎となる考え方、アルゴリズムを理解しているだろうか？ ITエンジニアに贈る、アルゴリズム入門。

[鹿野恵祐，＠IT]

　連載第1回「『＋1』だけで四則演算をするには？」に引き続き、プログラミングにおけるアルゴリズムの重要性と面白さを紹介したいと思います。例としてプログラミングで頻繁に使われる並べ替えと検索のアルゴリズムを取り上げ、それぞれがどういった処理を行っているのか考えてみましょう。

　同じ問題でも解き方（アルゴリズム）によってかなりの速度の違いが出てくる可能性があることは、前回紹介したとおりです。今回は代表的な並べ替えのアルゴリズムを基にプログラムを作成し、実行にかかった時間を測定して、具体的な処理速度の違いをお見せしようと試みています。

　プログラミング言語では、すでに並べ替えの仕組みが用意されていることが多いので、このアルゴリズムをあまり意識していない人もいるのではないでしょうか。しかし、すべてのプログラミングの基本であるアルゴリズムを学んでおけば、今後プログラムを書く際にも、設計の際にも、必ず役に立つと思います。

マージソートとバブルソート

　並べ替え（ソート）とはその名のとおり、データの集合を一定の規則に従って並べ替えることです。名簿に載っている社員名をあいうえお順に並べたいとき、学校で生徒のテストの点数を高い順に並べたいとき、店舗で製品を売り上げ数が多い順に並べたいときなど、並べ替えが必要な状況はいろいろあるでしょう。

　並べ替えについては、さまざまな考え方に基づいた手法が研究されています。代表的な並べ替えのアルゴリズムには「バブルソート」「挿入ソート」「ヒープソート」「マージソート」「クイックソート」などがあります。それらを組み合わせた複合的な手法を取る場合もあります。今回はこの中からバブルソートとマージソートを取り上げます。

　前回、アルゴリズムの例として、トランプを並べ替える複数の方法を考えました。同じように今回もトランプを例に使います。トランプには4つのスート（マーク）がありますが、問題を簡単にするために、ハートのエース（A）〜キング（K）の13枚を使うことにしましょう。

　13枚のトランプが横1列に並んでいるとします。左から右へ向かって、「2･5･A･Q･7･3･4･K･9･8･10･6･J」という順番です。これを「A･2･3･4･5･6･7･8･9･10･J･Q･K」と、小さい順に並べ替えます。

　この問題を、2つのアルゴリズムで解いてみましょう。

バブルソート

　バブルソートは、一般的に遅いといわれている並べ替えのアルゴリズムです。

　左端のカードの数字と、左から2枚目のカードの数字を比較します。1枚目が2枚目より大きければ、カードを入れ替えます。次に、2枚目の数字と3枚目の数字を比較し、2枚目が3枚目より大きければ、カードを入れ替えます。これを繰り返すことで、より大きい数字のカードが右に寄っていき、最後には右端に一番大きな数字のカードが来ます。

　この処理を繰り返すことで、左端から小さい順にカードが並びます。

並べ替えの手順	カードの状態
左端のカードの「2」と 左から2枚目のカードの「5」を比較	「2･5･A･Q･7･3･4･K･9･8･10･6･J」
「2」は「5」より小さいので入れ替えない	「2･5･A･Q･7･3･4･K･9･8･10･6･J」
2枚目のカードの「5」と 3枚目のカードの「A」を比較	「2･5･A･Q･7･3･4･K･9･8･10･6･J」
「5」は「A」より大きいので入れ替える	「2･A･5･Q･7･3･4･K･9･8･10･6･J」
3枚目のカードになった「5」と 4枚目のカードの「Q」を比較	「2･A･5･Q･7･3･4･K･9･8･10･6･J」
……

　この処理を列の最後まで行うと、Kのカードが右端に来ます。再度この一連の処理を行うと、Qのカードが右端から2番目に来ます。3回目を行えばJのカードが右端から3番目に来ます。これを繰り返すことで、カードは左から「A･2･3･4･5･6･7･8･9･10･J･Q･K」の順に並びます。

このアルゴリズムを基に作成したソースファイルのダウンロード（C・Java）

マージソート