ソートアルゴリズム

ソートとは

今回は、ソートについて見ていきます。

ソートは、データを順番に並び替えることです。日本語では、整列、並べ替えなどと呼ばれます。例えば、次のように数字を順番に並べ替えたり、名前を名前の順に並び替えることもソートです。

ソートアルゴリズム

ソートアルゴリズムには、さまざまなものがあります。ここでは、最も単純なソートアルゴリズムであるバブルソートを見た後に、より効率的なマージソートを見ていきます。

バブルソート

バブルソートとは

バブルソートは、単純で実装も非常に簡単なソートアルゴリズムです。しかし、効率は非常に悪く、オーダーは、$O(n^2)$ です。

バブルソートのアルゴリズム

バブルソートは、隣り合う要素を比較しながらソートします。

はじめは、一番目の要素と二番目の要素を比較して、入れ替えます。

次は、一番目の要素と三番目の要素を比較して、入れ替えます。

一番目の要素と四番目の要素を比較して、入れ替えます。

二番目の要素と三番目の要素を比較して、入れ替えます。

二番目の要素と四番目の要素を比較して、入れ替えます。

三番目の要素と四番目の要素を比較して、入れ替えます。

これで、完全に並び替えられました。

これを一般化すると、次のようになります。 はじめは、一番目の要素と二番目の要素を比較して入れ替えます。つぎは一番目と三番目、さらにつぎは一番目と四番目、…、一番目と n 番目と比較して入れ替えていきます。 その後、二番目と三番目、二番目と四番目、…、二番目と n 番目と入れ替えていきます。さらに、これを n-1 番目と n 番目まで繰り返していけば、ソートできます。

バブルソートのプログラム

バブルソートのアルゴリズムを実装すると、次のようになります。非常に簡単ですね。

練習問題

バブルソートを用いて、データを降順に並び替える関数を作ってみましょう。

解答

マージソート

マージソートとは

マージソートは、アルゴリズム自体はバブルソートより複雑ですが非常に効率の良いアルゴリズムです。バブルソートのオーダーが、$O(n^2)$ であったのに対して、マージソートのオーダーは $O(n\log n)$ です。非常に速いですね。併合整列法と呼ばれることもあるようです。

マージソートのアルゴリズム

基本的な流れとしては、次のようになります。以下を再帰的に行えばソートできます。

1. データ列を二分割する。
2. それぞれのデータ列をソートする。
3. ソートされた 2 つのデータをマージする。

実際に、簡単な例を見てみましょう。

まずは、データ列を二分割することを繰り返していきます。

次に、分割した要素を並べ替えながら戻していきます。まずは、バラバラの要素を二つずつの組に戻していきます。この時、並び替えも行います。

次に、二つずつの組をさらに戻していきます。

マージソートのプログラム

マージソートのプログラムを作ってみましょう。

データを二分割してそれぞれのデータ列をソートしていくのは、再帰を使えば良さそうです。配列の長さが 1 以下になった時には、そのデータをそのまま返せば良さそうです。

マージする処理はどうすれば良いでしょう。これも再帰を使うと、簡単にできます。二つのデータはそれぞれソートされているので、二つのはじめのデータを比較して小さい方の数を取り出し、残りを再帰的にマージします。

これを基に、プログラムを作ると、次のようになります。

+ 演算子を用いることで二つの配列を一つに結合することができます。

a[i:j] とすることで、配列 a の i 番目から j - 1 番目の要素を取り出すことができます。ちなみに、開始インデックスや終了インデックスは省略することもできます。

マージソートの計算量

merge 関数の計算量は、$O(n)$ となります。

merge_sort 関数は、再帰になっていますが、毎回データ量が半分になっているので、おおよそ $\log_2 n$ 回 merge 関数を呼び出しています。よって、計算量は $O(n\log n)$ です。

練習問題

マージソートを用いて、データを降順に並び替える関数を作ってみましょう。

解答

ソートライブラリ

Python にはソートをする関数が備わっています。sort と sorted があります。

sort

次のようにすることで、配列のデータをソートすることができます。

sorted

sorted 関数は、要素を並び替えた配列を返します。

注記

実は、ここで紹介した以外にもたくさんのソートアルゴリズムがあります。

バブルソート、マージソートの他に、クイックソートや選択ソート、挿入ソート、ヒープソート、バケットソートなどがあります。

他にも、非常に効率の悪いソートアルゴリズムとして、ボゴソートが知られています。ボゴソートは、ソートが完了するまで配列の中身をランダムにシャッフルすることを繰り返すというものです。いつになったら、ソートが完了するのでしょう(笑)

これは、昔に話題になった動画です。いろいろなソートアルゴリズムを視覚的にわかりやすく比較しています。最後のソートアルゴリズムは必見です。