2

コーメンらによるアルゴリズム入門を読んでいます。al。そして、彼らが基数ソートを説明している部分で、彼らは言います：

直感的には、最上位桁で数字を並べ替え、結果の各ビンを再帰的に並べ替えてから、デッキを順番に組み合わせることができます。残念ながら、10個のビンのうち9個のカードは、各ビンを並べ替えるために取っておかなければならないため、この手順では、追跡する必要のあるカードの中間の山が多数生成されます。

これは何を意味するのでしょうか？MSBによる並べ替えがどのように問題になるのかわかりませんか？

4

2 に答える 2

2

並べ替える次のリストの例を検討してください：170、045、075、090、002、024、802、066、182、332、140、144

  • 最上位桁（数百）で並べ替えると、次のようになります。

    • ゼロ百バケット：045、075、090、002、024、066

    • 100バケット：170、182、140、144

    • 300バケット：332

    • 800バケット：802

  • ゼロバケットと100バケットの数値には、次の桁で並べ替える必要があります（他の2つのバケットにはそれぞれ1つのアイテムしか含まれていません）。

    • ゼロテン：002
    • 20代：024
    • 40代：045
    • 60年代：066
    • 70年代：075
    • 90年代：090

  • 複数の数値を持つ10のバケットがないため、最下位桁（1の位）で並べ替える必要はありません。ただし、100個のバケットの場合はそうではありません（演習：自分で再帰的に並べ替えます）。したがって、現在ソートされているゼロ百バケットは連結され、順番に結合され、1、3、および800バケットで次のようになります。

    002, 024, 045, 066, 075, 090, 140, 144, 170, 182, 332, 801

著者が、LSD基数ソートでは必要のない中間の再帰的ソートステップを参照していることがわかります。

于 2012-10-15T06:02:22.317 に答える
1

これらは、LSD基数ソートの便利なプロパティを参照しており、各ソートステップが安定していることを確認できるため、配列全体で各桁に対して1つのステップを実行するだけで済み、サブセットを個別にソートする必要はありません。

Michaelのサンプルデータを取得するには：

0ステップ後：

170、045、075、090、002、024、802、066、182、332、140、144

1ステップ後（単位で並べ替え）：

170、090、140、002、802、182、332、024、144、045、075、066

2つのステップの後（数十でソート）：

002、802、024、332、140、144、045、066、170、075、182、090

3つのステップの後（数百でソート）：

002、024、045、066、075、090、140、144、170、182、332、802

このプロパティは、基数10ではなくバイナリで基数ソートを行う場合に特に便利です。各ソートステップは、2つに分割するだけで、非常に簡単です。少なくとも、余分なメモリを使用せずにそれを実行したいまでです。

もちろん、MSD基数ソートは機能しますが、より多くの簿記および/または非末尾再帰が必要です。CLRS（他のエキスパートプログラマーと共通）が必要になるまで面倒な作業をしたくないという点で、これは「問題」にすぎません。

于 2012-10-15T09:07:59.463 に答える