4

4 桁ごとに 7 つの数字をソートする必要がある場合、最悪の場合、何回の比較が必要になりますか?(基数ソート) オプションは 40、38、47、280 です。

私の解決策 - 10 個のバケット (0 から 9)(リンクされたリスト) を取得しました。次に、i 桁のすべての数値について、その桁の値に対応するバケットに入れました。次に、それらの数値を配列に集めました。このプロセスがすべての数字に対して繰り返されるため、元の配列がソートされます。比較の総数 = 10*4=40 (対応するバケットを探すためにすべてのバケットを繰り返し処理したため、10)。

ここでの問題は、Timothy J Williams の本にあります。比較の数 = 桁数 * 数の数 * バケットの数 = 4*7*10=280 です。私は理解することができません。誰かがこれがどのように来たのか説明してもらえますか.

4

1 に答える 1

2

基数ソートが比較ベースのアルゴリズムではないことは事実です。ここでの比較は、反復に含まれる比較を説明します。まず、7 つの要素の配列をトラバースし、各数値の桁を適切なバケットに保持する必要があります。ここで、配列をトラバースするには、7 回の比較が必要です。すべての要素を 0 ～ 9 のバケットに配置した後、0 ～ 9 のすべてのバケットをトラバースし、バケット番号に従って要素を並べ替える必要があります。これには、0 ～ 9 のバケットをトラバースするのに 10 回の比較が必要です。7 つの要素の 4 桁すべてについて、このプロセスを繰り返さなければなりません。したがって、比較の総数は 7*10*4 = 280 になります。

于 2017-08-02T05:18:21.257 に答える