10

ウィキペディアのクイックソートのスペースの複雑さの説明で私が理解したことから、クイックソートのスペースの複雑さはその再帰的な性質に由来します。クイックソートを非再帰的に実装することが可能かどうか、そしてそうすることで、一定のスペースの複雑さでそれを実装することが可能かどうかについて興味があります。

4

3 に答える 3

18

ウィキペディアは必ずしも間違っているわけではありません。そして、セクションが示唆するように、一定のスペースを使用して、クイックソートまたは同様のことを行う方法があります。1つの重要なポイント。クイックソート自体は、再帰的パーティショニングアルゴリズムとして定義できます。その場合、定義上、O（n）スタックスペースが必要になります。しかし、私はあなたがそのような衒学的な定義を使用していないと仮定しています。

パーティショニングがどのように機能するかを簡単に確認します。配列、開始点、および終了点が与えられると、パーティション値が選択されます。次に、配列内のデータ要素が分割されるため、パーティション値よりも小さいものはすべて左側にあり、それよりも大きいものはすべて右側にあります。これを行う良い方法は、両端から始めて、属していない最初の値を見つけて、それらを交換することです。ちなみに、これは一定のスペースを使用します。

したがって、アルゴリズムの各ステップは配列を通過します。この事実を思い出しましょう。

これで、興味深い観察を行うことができます。深さ優先方式で再帰的分割を行う場合は、各範囲のエンドポイントのみを保存する必要があります。降りる途中で、配列の左端が常に始まりになります。交換できる要素が2つだけになるまで、終点は最初に近づきます。この時点で、最初は2つのスロットに移動しますが、最後はわかりません。だから、終わりを調べて、プロセスを続けてください。次に、次のステップ「アップ」で、次のエンドポイントが必要になります。

問題は、実際の値をスタックに格納する以外の方法で終わりを見つけることができるかどうかです。

ええと、答えは「はい」です。

再帰的パーティショニングアルゴリズムの各ステップは、すべてのデータを読み取ります。データに対していくつかの追加の計算を行うことができます。特に、最大値と2番目に大きい値を計算できます。（最小値も計算しますが、これは最適化です。）

値を使用して行うのは、範囲をマークすることです。最初の分割では、これは、分割点に2番目に大きい値を配置し、範囲の最後に最大値を配置することを意味します。ツリーに戻る途中で、範囲がどこから始まるかがわかります。範囲の終わりは、その値よりも大きい最初の値です。

出来上がり！データを保存せずに「再帰」ツリーを上に移動できます。提示されたデータを使用しているだけです。

これを実行したら、アルゴリズムを再帰的アルゴリズムからwhileループに変更するだけです。whileループはデータを再配置し、各ステップで開始点と停止点を設定します。スプリッターを選択し、データを分割し、開始点と終了点をマークしてから、データの左側で繰り返します。

最小単位に到達したら、それが完了したかどうかを確認します（データの最後に到達したかどうか）。そうでない場合は、1ユニット上のデータポイントを調べて、最初のマーカーを見つけます。次に、データを調べてエンドポイントを探します。ちなみに、この検索は、データの分割と複雑さの点で同等であるため、複雑さの順序を追加することはありません。次に、この配列を繰り返し処理し、完了するまでプロセスを続行します。

データに重複がある場合、プロセスは少し複雑になります。ただし、log（N）の重複がある場合は、重複を削除し、残りのスロットをスタックとして使用してデータを並べ替えてから、それらを元に戻すことについてほぼ議論します。

なぜこれがクイックソートなのか。クイックソートアルゴリズムは、パーティション交換アルゴリズムです。アルゴリズムは、スプリッター値を選択し、データを両側で分割し、このプロセスを繰り返すことによって進行します。ジェフリーが彼の答えで指摘しているように、再帰は必要ありません。とても便利です。

このアルゴリズムはまったく同じように進行します。パーティショニングは同じ基本ルールに従い、左側に小さいレコード、右側に大きいレコードがあります。唯一の違いは、各パーティション内で、特定の値がパーティションの端にあるように選択されることです。これらの値を注意深く配置することにより、追加の「ステップごとの」ストレージは必要ありません。これらの値はパーティションに属しているため、partition-and-repeatのクイックソートプリンシパルによると、これは有効なパーティションです。

クイックソートで再帰を使用する必要があると主張する場合、これはその厳密なテストに失敗します（元の質問への答えは簡単です）。

于 2012-07-13T01:35:29.760 に答える
5

非再帰的に実装することは完全に可能ですが、通常の関数呼び出し/戻りスタックとは別のスタックを実装することによってそれを行います。多くの（ほとんど同じ）関数の差出人アドレスではなく、重要な情報のみを格納することでスペースを節約できますが、そのサイズは一定ではなく対数になります。

于 2012-07-12T15:31:38.497 に答える
2

BranislavĎurianは1986年にクイックソートの定数スペースバージョンを発表しました。彼の論文「スタックなしのクイックソート」を参照してください。J. Gruska、B。Rovan、およびJ. Wiedermannの編集者、コンピュータサイエンスの数学的基礎の議事録、コンピュータサイエンスの講義ノートの第233巻、283〜289ページ。Springer-Verlag、1986年。

他の何人かの著者がこれをフォローアップしました。Bing-Chao and Knuth（1986）を探すことができます。ウェグナー（1987）; Kaldewaij and Udding（1991）; グリーズ（1994）。

于 2020-08-30T11:52:55.567 に答える