第2回　ソート処理時間、選ぶアルゴリズムでこんな差が！

鹿野恵祐
2007/10/18

プログラミングの基礎となる考え方、アルゴリズムを理解しているだろうか？ 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）

マージソート

　マージソートは数ある並べ替えの中で、比較的速いといわれているアルゴリズムです。並べ替え対象を分割した後、隣り合ったもの同士を小さい順に並べ（マージ）、出来上がったグループ同士を比較して小さい順に並べるという処理を繰り返すというものです。

　横1列に並んだトランプを、だいたい同じ枚数になるように2つに分けます。1つのグループの枚数が2枚以上であればさらに2つに分け、カードを1枚ずつにします。

　左端のカードの数字と、左から2枚目のカードの数字を比較します。数字が小さい方のカードを左端に、大きい方のカードを左から2枚目に置きます。次に、左から3枚目、4枚目のカードでも同じことを行います。各グループ内で、2枚のカードが小さい順に並ぶことになります。

　次にこのグループ同士を比較し、4枚のカードを小さい順に並べます。

　これを繰り返していくと、最終的には左端から小さい順にカードが並びます。

並べ替えの手順	カードの状態
カードを2つに分ける	「2･5･A･Q･7･3」「4･K･9･8･10･6･J」
左側のカードをさらに2つに分け、 これを繰り返す	「2･5･A」「Q･7･3」「4･K･9･8･10･6･J」
	「2･5」「A」「Q･7･3」「4･K･9･8･10･6･J」
	「2」「5」「A」「Q･7･3」「4･K･9･8･10･6･J」
左端のカードの「2」と 左から2枚目のカードの「5」を比較	「2」「5」「A」「Q･7･3」「4･K･9･8･10･6･J」
小さい「2」を左端に、 大きい「5」を左から2枚目に置く （小さい順に並べ替える）	「2･5」「A」「Q･7･3」「4･K･9･8･10･6･J」
「2･5」「A」を比較し、小さい順に並べ替える	「A･2･5」「Q･7･3」「4･K･9･8･10･6･J」
……

　このようにして次は「Q･7･3」を処理して「3･7･Q」とし、「A･2･5」「3･7･Q」を処理して「A･2･3･5･7･Q」とします。後半の7枚のカードも分割後マージし、「4･6･8･9･10･J･K」とします。最後に「A･2･3･5･7･Q」「4･6･8･9･10･J･K」をマージすると、カードは「A･2･3･4･5･6･7･8･9･10･J･Q･K」の順に並びます。

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

■データ件数10倍で、実行時間は何倍？

　これらのアルゴリズムを基に、C言語で2種類のプログラムを作成し（上記からダウンロードも可能です）、その実行時間を測定しました（実行ごとに乱数を発生させ、ソート用のデータを作成していますので、その時間も含まれています）。

要素数		10000	20000	30000	40000	50000	60000	70000	80000	90000	100000
バブル ソート	1回目	1.89	7.52	16.96	30.16	48.53	68.25	104.45	138.71	189.17	241.17
	2回目	1.88	7.54	16.97	30.18	47.27	67.95	98.98	142.76	185.88	241.46
	3回目	1.89	7.55	16.94	30.19	47.22	71.05	104.24	137.81	186.82	240.98
	平均	1.89	7.54	16.96	30.18	47.67	69.08	102.56	139.76	187.29	241.20
	差分	1.89	5.65	9.42	13.22	17.50	21.41	33.47	37.20	47.53	53.91
マージ ソート	1回目	0.01	0.02	0.03	0.06	0.07	0.08	0.1	0.11	0.12	0.14
	2回目	0.01	0.02	0.04	0.05	0.07	0.09	0.1	0.11	0.13	0.14
	3回目	0.01	0.03	0.04	0.05	0.07	0.09	0.1	0.12	0.13	0.14
	平均	0.01	0.02	0.04	0.05	0.07	0.09	0.10	0.11	0.13	0.14
	差分	0.01	0.01	0.01	0.02	0.02	0.02	0.01	0.01	0.01	0.01
バブル ソート （別PC）	1回目	0.56	2.22	4.98	8.88	13.82	19.91	27.11	35.38	44.87	55.35
	2回目	0.55	2.21	4.99	8.86	13.84	19.94	27.2	35.49	44.87	55.42
	3回目	0.55	2.21	4.98	8.86	13.89	19.92	27.13	35.49	44.87	55.39
	平均	0.55	2.21	4.98	8.87	13.85	19.92	27.15	35.45	44.87	55.39
	差分	0.55	1.66	2.77	3.88	4.98	6.07	7.22	8.31	9.42	10.52

図1　ソート処理の速度

　アルゴリズムの違いによって大きく処理時間が異なることが、グラフから読み取れます。バブルソートは要素数が増えれば増えるほど多くの時間がかかります。マージソートは要素数が増えても、10万件くらいまでなら時間の増加率はそれほど高くありません（参考までに追加しますと、100万件では約1.69秒、1000万件では約20.22秒、1億件では227.94秒という結果が出ました）。

　処理時間は、実行環境によっても変化します。そこでバブルソートについては、環境による速度の違いを調べるため、プロセッサの性能が4倍ほどの環境でも実行してみました。4倍程度の性能差では、アルゴリズムの違いによる差を吸収できていないことが分かります。

　従って、高速に処理を行いたいのであれば、それに適したアルゴリズムを選択するのが効果的であることが分かると思います（実際にはプログラムの実行速度は、プログラミングの方法、コンパイラの最適化の度合いによっても異なります）。

次は、文字列の検索をしてみよう

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）