安定性のあるソートアルゴリズム一覧 安定ソートとは? わかりやすく解説!

安定性のあるソートアルゴリズム一覧 安定ソートとは? わかりやすく解説!

 調べても安定性のあるソートアルゴリズムを1つのページにわかりやすくまとめてくれている記事を見つけれなかったので、同じように探している人のために記事にして残しておきます。

安定ソートとは?

 安定ソートとは、元のデータの順序を維持したままソートするアルゴリズムのこと。

 ゲームのスコアを例に挙げると、プレイヤーIDを昇順に並べた元のデータがあるとします。

ID名前スコア
1A3
2B8
3C8

 このデータをスコア順に並べた時、BとCが同じスコアになりますよね。

 安定ソートは元のプレイヤーID順を保持したままソートできるのでBの次にCを配置します。

例:安定ソートでスコアが高い順に並び替え

ID名前スコア
2B8
3C8
1A3

例:安定ではないソートでスコアが高い順に並び替え

ID名前スコア
3C8
2B8
1A3

安定性のあるソートアルゴリズム一覧

バブルソート (bubble sort)

 安定な内部ソート。基本交換法、隣接交換法ともいう。

最悪計算時間 O(n2)
最良計算時間 O(n)
平均計算時間 O(n2)
最悪空間計算量 O(1) auxiliary

シェーカーソート (shaker sort)

 安定な内部ソート。バブルソートの改良版。

挿入ソートインサーションソート

 クイックソートやマージソートに比べて遅い。しかし、実装が容易のため利用されることがある。

最悪計算時間 O(n2)
最良計算時間 O(n)
平均計算時間 O(n2)
最悪空間計算量 O(n) total,O(1) auxiliary

マージソート

 ランダムデータであればクイックソートの方が速い。

最悪計算時間 O(nlogn)
最良計算時間 O(nlogn)
平均計算時間 O(nlogn)
最悪空間計算量 O(n)

安定性のないソートアルゴリズム一覧

コムソート(comb sort)

 バブルソートの改良版。実行速度はほぼO(nlogn) になる。

選択ソート(selection sort)

 安定ではない内部ソート。

最悪計算時間 O(n2)
最良計算時間 O(n2)
平均計算時間 O(n2)
最悪空間計算量 О(n) total, O(1) auxiliary

シェルソート(Shellsort, Shell sort, Shell’s method)

最悪計算時間 間隔に依存
最良計算時間 O(nlogn)
平均計算時間 間隔に依存
最悪空間計算量 О(1)

クイックソート (quicksort)

最悪計算時間 O(n2)
最良計算時間 O(nlogn)
平均計算時間 O(nlogn)
最悪空間計算量 О(n)