algorithm => 並べ替え

パラメーター

パラメータ	説明
安定	並べ替えアルゴリズムは、ソート後に等しい要素の相対的な順序を保持すると安定します。
所定の位置に	並べ替えアルゴリズムは、 `O(1)`補助メモリ（ソートする必要のあるアレイを数えない`O(1)`のみを使用してソートすると、その場で実行されます。
最良の複雑さ	ソーティングアルゴリズムは、その実行時間がすべての可能な入力に対して少なくとも `T(n)` である場合、 `O(T(n))`最良のケース時間複雑性を有する。
平均ケース複雑度	すべての可能な入力にわたって平均化されたその実行時間が`T(n)`場合、ソートアルゴリズムは平均ケース時間複雑度`O(T(n))` 有する。
最悪の場合の複雑さ	ソーティングアルゴリズムは、その実行時間が最大で `T(n)` である場合、 `O(T(n))`最悪の時間複雑度を`T(n)` 。

ソートの安定性とは、ソートアルゴリズムが元の入力の等価キーの相対順序を結果出力に保持するかどうかを意味します。

したがってソートアルゴリズムは、等価キーを持つ2つのオブジェクトが、ソートされていない配列に表示されているソートされた出力で同じ順序で表示される場合に安定していると言われています。

ペアのリストを考えてみましょう：

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

ここでは、各ペアの最初の要素を使用してリストをソートします。

このリストを安定してソートすると、以下のリストが出力されます：

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

元のリストでも(9, 7) (9, 3)後に(9, 7) (9, 3)が表示されるためです。

不安定な並べ替えは、以下のリストを出力します：

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

不安定なソートは、安定したソートと同じ出力を生成することがありますが、必ずしもそうではありません。

よく知られている安定したソート：

よく知られている不安定な並べ替え：

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow