1つの一時変数/スペースを使用して配列をソートすることはできますか？

Question

配列がa1、a2、...、ak、_、a（k + 1）、...、anで与えられているとします。 アンダースコア（_）は空白を表します。配列要素をこの空間に移動できます。この操作を何回でも繰り返すことができます。 1つの空白スペースですべての配列をソートすることは可能ですか？

Answer 1

はい、可能です。

ソートされた配列は、その配列の特定の順列に過ぎません。

個々のスワップ順に並べ替えることができます。

スワップは、単一の一時要素で実装できます。

（実際には、の配列を、XOR演算を使用してを一時的にソートすることは可能です）。

Answer 2

インプレースソートにはいくつかのアルゴリズムがあります。最も顕著なのはクイックソートの非再帰バージョンです（再帰バージョンは再帰呼び出しの数に比例してスタック上の領域を占有するため）。平均してO（n log n）の複雑さが与えられます。

もう1つの可能性は、コンパイル性がO（n^2）である挿入ソートやバブルソートなど、効率の悪いアルゴリズムを使用することです。

あなたの特定の質問については、その特定のスペースを使用することですが、あなたはBathshebaのように交換することができますが、私はこの種の操作を行う時間を失うことはありません。

配列の途中に明示的に "未使用領域"という概念がある場合は、その意味論、つまり順序​​付けの正しい配置が何であるかを理解するようにしてください。あなたがいなくて、どこにいてもそれを残してしまうと、あなたは "壊れた"不変式を見つけることになり、あなたのコレクションにバイナリ検索のようなアルゴリズムを実装するのが難しくなります。

Answer 3

私はこのようなコンテナを実際のコードで見たことはありませんが、実装する最も簡単なアルゴリズムは、空の最初の要素と交換し、コンテナは2番目の位置から始まり、最後の位置まで繰り返されます。最後の位置は空のスペースになります。この場合、スワップするだけで、空白を埋めることができ、他の位置を空にすることができます。