【アルゴリズム基礎】6種の基本ソート処理で計算量オーダー比較

プログラムを高速に動作させるには、入力値を効率良く制御できるアルゴリズムを考える必要があるので、今回は基本的なソートアルゴリズムを実装して、計算量Oを確認してみます。

またアルゴリズムは以下2つの計算量で評価。

◼︎ 時間計算量

・プログラム実行に必要な時間.

◼︎ 領域計算量

・プログラム実行に必要な領域.

一般的に時間計算量と領域計算量はトレードオフの関係と言われます。

TaNA
以前に比べればハードウェアが随分発展してるので、領域計算量より時間計算量を重視する傾向が高いでしょうか。私は普段、領域計算量は考慮出来ていないかも…

また単に計算量(オーダー)と行った場合は時間計算量を指すようです。

計算量オーダーO.

計算量オーダーOとはアルゴリズムの効率を評価する指標の一つ。

◼︎ O(n) / 線形時間

・データ量だけ時間がかかる.

・forループ1回分.

◼︎ O(logn) / 対数時間

・データ量が増えても計算量がほぼ変化しない.

・多くのケースでこれ以上改善の必要は無し.

◼︎ O(nlogn) / 準線形時間

・線形*対数なのでデータ量が増えても計算量はほぼ変化しない.

◼︎ O(n^2) / 二乗時間

・forループ2回分.

・これ以上は処理が重すぎて使いづらい.

◼︎ O(n!) / 階乗時間

・入力値nに比例して随分重くなる.

階乗系は入力値に比例して重いので、スパコンでも数百年かかるケースも…

O(logn) > O(n) > O(nlogn) > O(n^2) >>> (超えられない壁) >>> O(n!)

バブルソート.

配列の末尾から隣接要素の大小を比較し、大小関係が逆ならば並び替えを行うソートアルゴリズム。

未ソート部分の隣同士の比較は(n^2 – n)/2回なので、アルゴリズムの計算量O(n^2)。

挿入ソート.

挿入ソートは未ソート部分とソート済み部分に分け、以下の手順を繰り返す。

1. 未ソート部分の先頭から要素を1つ取り出しvに記録.

2. ソート済みの部分において、vより大きい要素を後方へ1つずつ移動.

3. 最後に空いた位置に「取り出した要素v」を挿入.

バブルソート同様、比較回数は(n^2 – n)/2回なので、アルゴリズムの計算量O(n^2)。

挿入ソートは初期の並び順に依存し、降順気味に並んでいるとO(n^2)、昇順だとO(n)に近付く。

選択ソート.

選択ソートはバブル・挿入同様、未ソート部分とソート済み部分に分け、以下の手順を繰り返す。

1. 未ソート部分列から最小の要素の位置minjを特定.

2. minjの位置にある要素と未ソート部分の先頭要素を交換.

バブル・挿入同様、比較回数は(n^2 – n)/2回なので、アルゴリズムの計算量O(n^2)。

シェルソート.

シェルソートは、ほぼ整列された集合に高速に動作する挿入ソートの特徴を活かしたアルゴリズム。

シェルソートでは、ある一定間隔gだけ離れた要素のみを対象とした挿入ソートを繰り返す。

間隔gの取り方で計算量が異なり、上の例では計算量O(n^1.25)になることが予測されます。

マージソート.

バブルソートのような初等的なアルゴリズムでは大量データに不向きです。

マージソートは大量データにも耐えうるアルゴリズムの一つ。

マージソートでは分割 + 再帰 + 統合の3ステップで計算量O(nlogn)を実現。

例えばデータ{9, 6, 7, 2, 5, 1, 8, 4, 2}の1個のデータになるまで分割してみる。

9 → 5 → 3 → 2 → 1の4分割が必要となり、出来上がる階層は5階層。

n個のデータに対しておおよそlogn個の階層となり、各階層のマージ処理は計算量O(n)。

そのため合計の計算量O(nlogn)となります。

ただ入力値を保持する領域とは別の一時的なメモリ領域が必要なソートアルゴリズム。

クイックソート.

クイックソートは以下のように分割統治法を利用したアルゴリズム。

1. patitonによって、対象の部分配列を前後2つの部分配列に分割.

2. 前方の部分配列に対してクイックソートを実行.

3. 後方の部分配列に対してクイックソートを実行.

マージソート同様、再帰的にpatitonを実行。

マージソートとは異なり、追加のメモリ領域は不要なインプレースソートという特徴があります。

TaNA
再帰処理って何が嬉しいのか、新人の頃はよく理解出来ていませんでしたが、アルゴリズムにおける計算量の観点で考えると、非常に大切な要素だと分かります。

ちなみに計算量O(nlogn)となり、一般的に最も高速なアルゴリズムと言われます。