Radixソートを再帰的に実装する - 最後に要素を印刷する方法は？

Question

注：

私はすでにこのプログラムの開発before上の具体的な質問をし、今私は非常に最後のステップでこだわっていると私はそれのための新しいスレッドを開くために、より良いかもしれませんね。

説明：

Iは、（これは基本的には基数ソートである）を再帰的に0から99999までの数字をソートするプログラムの開発を実現するために必要です。プロセス自体はまったく同じです：ユーザーはメインメソッドのそれらの数値を含む配列をタイプします。次に、mainメソッドはsortメソッドを呼び出します。ここでは、10行1列の 'space'という2次元配列を作成します。次に、配列内のすべての数値を最初の実行で10.000になる桁で除算します。たとえば、23456/10000 = 2,3456 = 2（java）の場合、プログラムはこの数をスペース[2] [0]に入れます。次に、この行全体を取り出し、それを拡張します。これはputInBucketメソッドで行われます。これは、同じ行に別の番号を入れることができるようにするためです。

「numbers」配列の内側にあるすべての番号に対してこれを行います。次に、これらの行を処理して同じ原則で再度ソートするとしますが、ここで2桁目を見ていきます。私たちは、右から左へではなく、左から右にこれをしたいと思っています。我々はそうするためには3と4を​​比較したいと思います、私たちの第二列は、この

[23456、24567]のようになります場合

ので、私たちは、各再帰で桁/ 10を計算しますコール。数字が0の場合は、もう並べ替えるものはありません。

再帰呼び出し自体は、0から9の行で動作します。ここでは、以前に異なる数値を入れて、別の行に入れて並べ替えます。

質問：

私はプログラムの開発は、行うことになっているものんだと思います。残念ながら、結果を適切に印刷する方法はわかりません。たとえば、以下のコードでは、メインメソッドでバケットを印刷しようとしましたが、ちょうど私が入力した配列だけが正確に表示されるので、正しいとは限りません。

行9のすべての要素で開始する必要があります。この行に複数の数値が含まれている場合は、再帰呼び出しの結果で並べ替える必要があります。

これを正しく実装する方法を知っている人はいますか？前もって感謝します！

public static int[] sort(int[] numbers, int digit) { 

    if (numbers.length <= 1 || digits == 0) 
    return numbers; 

    int[][]space = new int[10][1]; 
    int i, j = 0; 

    for (j = 0; j < numbers.length; j++) { 
    i = numbers[j]/digit % 10; 
    space[i][0] = numbers[j]; 
    space[i] = putInBucket(space[i], numbers[j]); 
    } 

    digit = digit/10; 

    for (i = 0; i < 9; i++) { 
    sort(space[i], digit); 
    } 

    return numbers 

} 

private static int[] putInBucket(int[] bucket, int number) { 

    int[] bucket_new = new int[bucket.length+1]; 

    for (int i = 1; i < bucket_new.length; i++) { 
    bucket_new[i] = bucket[i-1]; 
    } 

    return bucket_new; 

} 

public static void main (String [] argv) { 

    int[] numbers = IO.readInts("Numbers: "); 
    int digit = 10000; 
    int[] bucket = sort(numbers, digit); 

    for (int i = 0; i < bucket.length; i++) { 
    System.out.println(bucket[i]); 

} 

Answer 1

私はあなたの前の質問に私のanswerで実証されているように、あなたはソートnumbersを返却する必要があります。ソートされた数値は、spaceから、最小の数字から最大の数字に移動して取得します。そのために

int k = 0; 

    for (i = 0; i < 10; i++) { 
     for (j = 0; j < len[i]; j++) { 
      numbers[k] = space[i][j]; 
      k++; 
     } 
    } 

、あなたはおそらく、各桁（len[i]変数）用バケットの長さを追跡する必要があります。

完全なソリューションは、次のようになります。

public static int[] sort(int[] numbers, int digit) { 

    if (numbers.length == 0 || digit <= 0) 
      return numbers; 

    int[][]space = new int[10][1]; 
    int[] len = new int[10]; 
    int i, j = 0; 

     for (j = 0; j < numbers.length; j++) { 
      i = (numbers[j]/digit) % 10; 
      len[i]++; 
      space[i] = putInBucket(space[i], numbers[j]); 
     } 


     for (i = 0; i < 10; i++) { 
      int[] bucket = new int[len[i]]; 
      for (int k = 0; k < len[i]; k++) 
       bucket[k] = space[i][k]; 
      space[i] = sort(bucket, digit/10); 
     } 

     int k = 0; 

     for (i = 0; i < 10; i++) { 
      for (j = 0; j < len[i]; j++) { 
       numbers[k] = space[i][j]; 
       k++; 
      } 
     } 

     return numbers; 

} 

private static int[] putInBucket(int[] bucket, int number) { 

    int[] bucket_new = new int[bucket.length+1]; 


    for (int i = 1; i < bucket_new.length; i++) { 
     bucket_new[i] = bucket[i-1]; 
    } 
    bucket_new[0] = number; 

    return bucket_new; 

} 

Answer 2

ソートでは、ローカルの空間インスタンスが更新されていますが、更新されていない入力パラメータ番号が返されています。

私は空間をスペース[10] [0]として初期化する必要があると考えています。空間のもう1つの行にデータがない可能性があるからです。

これは左から右（最下位の数字の最初）の基数ソートになっていますか？通常、それは反復を介して行われます（ちょうど各外側のループ上の数字にスペースをコピーしてください）。左から右への基数の並べ替え（最も重要な数字の最初の）は、しばしば再帰を使用して行われます。

Bijay Gurungのsort（）はやや単純化できます。コメントで指摘の変更：

public static int[] sort(int[] numbers, int digit) { 
    if (numbers.length == 0 || digit <= 0) 
     return numbers; 
    int[][]space = new int[10][0]; // [1] => [0] 
    int[] len = new int[10]; 
    int i, j; 
    for (j = 0; j < numbers.length; j++) { 
     i = (numbers[j]/digit) % 10; 
     len[i]++; 
     space[i] = putInBucket(space[i], numbers[j]); 
    } 
    for (i = 0; i < 10; i++) { 
    // int[] bucket = new int[len[i]];  // deleted 
    // for (int k = 0; k < len[i]; k++)  // deleted 
    //  bucket[k] = space[i][k];   // deleted 
     space[i] = sort(space[i], digit/10); // bucket => space[i] 
    } 
    int k = 0; 
    for (i = 0; i < 10; i++) { 
     for (j = 0; j < len[i]; j++) { 
      numbers[k] = space[i][j]; 
      k++; 
     } 
    } 
    return numbers; 
}