アルゴリズムとは「何らかの問題を解決するために考えらえた手順や計算方法」のことです。アルゴリズムを習得することで、日常生活や業務の中での問題解決に役立てることができたり、特にプログラミング能力の向上には大きく寄与します。
本記事では最も基本的なアルゴリズムの１つ、ソートアルゴリズムについて解説します。
ソートアルゴリズムとは？
アルゴリズムの中で最も基本的なものが「ソート（整理、並べ替え）」です。
データベースをはじめ、大量のデータを扱う機会は少なくありません。その際に、データを昇順、降順など、一定の規則に従って整列させる必要があります。そのための技術がソートアルゴリズムです。
代表的なソートアルゴリズムとして知られる「バブルソート」「クイックソート」「マージソート」「選択ソート」「挿入ソート」「ヒープソート」について解説していきます。
バブルソート
隣接する値どうしの比較、入れ替えを繰り返すことで、値を大きい順または小さい順に整列させる方法をバブルソートと呼びます。
例) (9, 7, 6, 8, 5, 3)を昇順にソート(配列)する
- (9, 7, 6, 8, 5, 3) この並び順でスタート
- (9, 7, 6, 8, 3, 5) 5と3を比較・交換
- (9, 7, 6, 3, 8, 5) 8と3を比較・交換
- (9, 7, 3, 6, 8, 5) 6と3を比較・交換
- (9, 3, 7, 6, 8, 5) 7と3を比較・交換
- (3, 9, 7, 6, 8, 5) 9と3を比較・交換、先頭要素が確定
- (3, 9, 7, 6, 5, 8) 8と5を比較・交換
- (3, 9, 7, 5, 6, 8) 6と5を比較・交換
- (3, 9, 5, 7, 6, 8) 7と5を比較・交換
- (3, 5, 9, 7, 6, 8) 9と5を比較・交換、先頭から2番目の要素が確定
- (3, 5, 9, 6, 7, 8) 7と6を比較・交換
- (3, 5, 6, 9, 7, 8) 9と6を比較・交換、先頭から3番目の要素が確定
- (3, 5, 6, 7, 9, 8) 9と7を比較・交換、先頭から4番目の要素が確定
- (3, 5, 6, 7, 8, 9) 9と8を比較・交換、5番目、6番目の要素が確定 ★昇順ソート完了★
このような手順によって数値を整列するのがバブルソートです（並べ替えの過程で数字が右から左へ移動していく様子が、泡（バブル）がフワフワと浮かんでいくように見えることから名づけられたそうです）。
計算回数
バブルソートでは、必ずn(n-1)/2回の比較が行われます。
したがって、計算回数のオーダーはO(n^2)であることが分かります。
クイックソート
上記のバブルソートよりも高速な値の整列を実現するアルゴリズムがクイックソートです。このアルゴリズムでは、ピボットと呼ばれる基準値を決め、データ群を基準以上と基準未満の2つのグループに分割し、処理を繰り返すことで要素を入れ替えていきます。
例)(5, 9, 8, 3)を昇順にソート(配列)する
ピボット(基準値)の決め方は一通りではありませんが、今回は「先頭の2つの値のうち大きい値を選ぶ」というルールで実施してみます。
- 先頭の異なる2つの値に着目すると5と9があり、そのうち大きい値となる9をピボットとして取ります。先頭から9以上の値を探索すると9（先頭から2番目の要素）が見つかり、末尾から9未満の値を探索すると3（末尾の要素）が見つかります。そこで9と3を交換して、「5, 3, 8, 9」と整列します。
5 9 8 3 ⇒ 5 3 8 9 - 続いて、先頭から3番目以降の要素から9以上の値を探索すると9が見つかり、末尾から2番目から前方に向かって9未満の値を探索すると8が見つかります。ただし、探索位置が交差してしまったため、探索位置が交差した8と9の間で数列を分割して「5, 3, 8」「9」と整列します。このように数列を分割することで、1つの数列を基準値未満のグループ「5, 3, 8」と基準値以上のグループ「9」に分割されました。
「5, 3, 8, 9」 ⇒ 「5, 3, 8」「9」 - ルールに基づいて「5, 3, 8」の中で5をピボットに取り、先頭から探索して見つかった5と、末尾から探索して見つかった3を交換して「3, 5, 8」と整列します。
「5, 3, 8」「9」 ⇒ 「3, 5, 8」「9」 - さらに探索を続けると3と5の探索位置が交差したので、「3」「5,8」を分割します。
「3, 5, 8」「9」 ⇒ 「3」「5, 8」「9」 - 「5, 8」にて8をピボットに取り、探索位置が交差する5と8の間で分割して「5」と「8」となります。
「3」「5, 8」「9」 ⇒ 「3」「5」「8」「9」
以上の流れを整理すると次のようになります。
「5, 9, 8, 3」
⇒「5, 3, 8, 9」
⇒「5, 3, 8」「9」
⇒「3, 5, 8」「9」
⇒「3」「5, 8」「9」
⇒「3」「5」「8」「9」
計算回数
クイックソートの計算回数は、平均でO(n log n)ですが、最悪のケースではO(n^2)であり、常に高いパフォーマンスを発揮できるわけではないというところは注意が必要ですが、一般的には高速なアルゴリズムとされています。
マージソート
マージソートとは、「まずデータを分割し、最小の単位からソート、併合（マージ）を繰り返しながら最終的に全体のソートをする」というアルゴリズムです。処理時間がデータの並びに大きな影響を受けないのが特徴です。
ただし、マージソートでは、マージをするために、元の配列とは別の新しい配列を準備する必要があり、そのための記憶領域も必要になる点には注意が必要です。
例)(9, 7, 6, 8, 5, 3, 4, 2)を昇順にソート(配列)する
- 初期値「9, 7, 6, 8, 5, 3, 4, 2」
- 分解 「9, 7, 6, 8」「5, 3, 4, 2」
- 分解 「9, 7」「6, 8」「5, 3」「4, 2」
- 分解 「9」「7」「6」「8」「5」「3」「4」「2」
- マージ「7, 9」「6, 8」「3, 5」「2, 4」
- マージ「6, 7, 8, 9 」「2, 3, 4, 5」
- マージ「2, 3, 4, 5, 6, 7, 8, 9」
マージソートは、問題を小さい部分問題に分けて考える分割統治法に基づくアルゴリズムです。分割統治法は、いくつかのプログラミング言語の標準ライブラリの要素として広く使われています。気になる方は「分割統治法」についても調べてみましょう。
計算回数
マージソートの計算回数は、最悪ケースでもO(n log n)となっています。
選択ソート
選択ソートは、「1番目の値から最後の値までの中の最小値を見つけ出し、1番目の要素と交換する。次に、2番目から最後の値までの中の最小値を見つけ出し、2番目の要素と交換する。次に3番目の…」という手順を繰り返してソートしていくアルゴリズムです。これは昇順にソートする場合の例ですが、「最小値を見つけ出す」⇒「最大値を見つけ出す」のように読み替えると、同様の手順で降順にソートすることができます。
例)(9,7,6,8,5,3)を昇順にソート（配列）する
- (9,7,6,8,5,3) この並び順でスタート
- (3,7,6,8,5,9) 最小値である3を発見、移動 1番目の要素が確定
- (3,5,6,8,7,9) 次に小さい値5を発見、移動 2番目の要素が確定
- (3,5,6,8,7,9) 次に小さい値6を発見、移動なし 3番目の要素が確定
- (3,5,6,7,8,9) 次に小さい値7を発見、移動 4番目の要素が確定
- (3,5,6,7,8,9) 次に小さい値8を発見、移動なし 5番目の要素が確定
- 残りが1つしかないので6番目の要素も確定
計算回数
比較回数は、n(n-1)/2です。つまり、O(n^2)であり、バブルソートと同じです。
しかし、交換回数は多くてもn-1回であり、バブルソートよりも高速です。
挿入ソート
挿入ソートは、「前から2個要素を取り出し、順序が逆なら入れ替える。次に3個目の値を取り出し、2個目までの中の適切な位置に挿入する。次に4個目の値を取り出し、3個目までの中の適切な位置に挿入する。…」という値の挿入を繰り返してソートしていくアルゴリズムです。
例)(9,7,6,8,5,3)を昇順にソート（配列）する
- (9,7,6,8,5,3) この並び順でスタート
- (7,9,6,8,5,3) 7と9を交換 3番目にある6をどうするか…
- (6,7,9,8,5,3) 6を先頭に挿入 4番目にある8をどうするか…
- (6,7,8,9,5,3) 8を3番目に挿入 5番目にある5をどうするか…
- (5,6,7,8,9,3) 5を先頭に挿入 6番目にある3をどうするか…
- (3,5,6,7,8,9) 3を先頭に挿入、確定
計算回数
比較回数は、最悪の場合にn(n-1)/2ですが、整列済みの部分が明確になっているデータに対してはこれよりも少なくて済みます。
バブルソートの場合、隣り合う値を比較・交換していきますが、挿入ソートでは適切な位置へ一発で挿入するため、ソート済み部分が多いとより有効なアルゴリズムになっています。
交換回数はバブルソートと同じです。したがって、適用するケースにもよりますが、バブルソートよりも高速であることが多いです。
ヒープソート
ヒープソートは以下のような手順でソートするアルゴリズムです。
- 未整列の配列から、ヒープ構造を構築する
※ヒープ構造…「子要素は親要素より常に大きいか等しい」状態になっている二分木構造 - ヒープの根（ルート）の数値を整列済み配列の最初に入れる
- 取り出した根（ルート）の位置を埋めるようにして、ヒープを再形成する
- 根（ルート）を整列済み配列に加える
- その後は３、４の手順を繰り返してソートしていきます。
「ヒープ構造を構築するための操作」、「ヒープ構造の再形成のための操作」にも本来は解説が必要なのですが、本記事ではいったん概要のみとさせていただきました。（解説をギブアップしました笑 コード付きの解説がウェブ上に多数掲載されていますので興味のある方は検索してみてください。）
ヒープ構造の中からルートを取り出していく処理のような、データの中から優先度の高いデータから順序通り取り出す仕組みは、一般に「優先度付きキュー」と呼ばれています。優先度付きキューは、様々なアプリケーションやアルゴリズムにも応用されている重要な考え方です。
計算回数
ヒープ構造を使うアルゴリズムは一般的に高速処理が特徴です。
ヒープソートの計算時間は、最悪ケースを考慮しても以下の通りとされています。
O(n log n)
アルゴリズムの重要性
アルゴリズムを学ぶ重要性とは何なのでしょうか？
プログラミングを例にあげるとすれば、それは「計算量の変化」にあります。この記事からもアルゴリズムを使うことで計算量を削減できること、どのアルゴリズムを選択するかによっても計算量が異なってくることを感じて頂けたならうれしいです。
さらに具体的な仕事の場面で考えると、システム開発では膨大なプログラムを必要とするため、1つ1つに効率的なアルゴリズムを適用することで、全体のパフォーマンスを大幅に向上できる利点があります。このため、プログラマーの資質として「アルゴリズムへの理解度」も問われるのは至極当然のことです。
プログラマーはもちろん、プログラミングをしない人もより効率的、効果的な業務のためにアルゴリズム学習を進めてみることをオススメします。
