安定ソート 【stable sort】 ステーブルソート

概要

安定ソート（stable sort）とは、並べ替え(ソート)アルゴリズムのうち、順位が同じ要素の並び順がソート前後で変わらない性質を持つもの。

ソートは複数のデータを何らかの順序に基いて順番通りになるよう整列させる処理で、数値の大小、文字列の辞書順、日付や時刻の新旧（前後）などの順序を用いて要素を並べ替えていく。どのような手順でソートを行うかをソートアルゴリズムと呼び、様々な手法が考案されている。

比較に用いる値が同じ要素が複数ある場合、それらは同じ順位に並ぶことになるが、整列の仕方によって元々並んでいた順番が必ず保存されるアルゴリズムと、途中で順番が入れ替わる（ことがある）アルゴリズムに分かれる。前者を安定ソート（stable sort）、後者を不安定ソート（unstable sort）という。

代表的な安定ソートとしてバブルソートや挿入ソート（インサーションソート）、基数ソート、シェーカーソートなどがあり、マージソートやバケットソートも実装によって安定とすることができる。不安定なソート法でも、元の並び順をデータとして与え、同順位の場合に比較させることで安定ソートとすることができる。