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

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

安定ソートとは？

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

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

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

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

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

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

　安定ソートでないソートはもともとのIDの並びを無視して並び替えてしまいます。

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

バブルソート (bubble sort)

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

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

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

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

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

マージソート

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

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

コムソート（comb sort）

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

選択ソート（selection sort）

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

シェルソート（Shellsort, Shell sort, Shell’s method）

クイックソート (quicksort)