|
安定ソート (stable sort) とは,「同じ値をもつデータのソート前の順序が,ソート後も変わらない」ようなソート・アルゴリズムの総称である.
例えばこの問題の場合には,アンケートの番号順に回答数を集計した配列を用意しておき,安定ソートによりソートすると,回答数が同じ項目はアンケートの番号順で並ぶようになる.
安定ソートの例としては,アルゴリズムが単純で実装が容易な挿入ソート (insertion sort) がある.
挿入ソートの基本的な考え方は,すでに並んでいるデータ a[0], ..., a[i-1] に対して,a[i] を左から順に比較していき,挿入場所(例えば、a[j] の直後に挿入すべきだったとする)がわかったら,その後ろの部分列 a[j + 1], a[j + 2], ..., a[i - 1] をずらして,空いた場所に a[i] を挿入する,というものである.