0

こんにちは私は私のコードを改善するためにいくつかの助けが必要です。基数ソートを使用して、たとえば10個の数値の配列を昇順で並べ替えようとしています。

サイズ10の配列でプログラムを実行し、10個のランダムな整数を次のように入力すると 70 309 450 279 799 192 586 609 54 657

私はこれを出します：

450 309 192 279 54 192 586 657 54 609

私のエラーがコードのどこにあるのかわからない。

class IntQueue
{

  static class Hlekkur
  {
    int tala;
    Hlekkur naest;
  }

  Hlekkur fyrsti;
  Hlekkur sidasti;
  int n;

  public IntQueue()
  {
    fyrsti = sidasti = null;
  }


  // First number in queue.
  public int first()
  {
    return fyrsti.tala;
  }


  public int get()
  {
    int res = fyrsti.tala;
    n--;
    if( fyrsti == sidasti )
      fyrsti = sidasti = null;
    else
      fyrsti = fyrsti.naest;
    return res;
  }


  public void put( int i )
  {
    Hlekkur nyr = new Hlekkur();
    n++;
    nyr.tala = i;
    if( sidasti==null )
    f yrsti = sidasti = nyr;
    else
    {
      sidasti.naest = nyr;
      sidasti = nyr;
    }
  }


  public int count()
  {
    return n;
  }

  public static void radixSort(int [] q, int n, int d){
    IntQueue [] queue = new IntQueue[n];

    for (int k = 0; k < n; k++){
      queue[k] = new IntQueue();
    }
    for (int i = d-1; i >=0; i--){
      for (int j = 0; j < n; j++){
        while(queue[j].count() != 0)
        {
          queue[j].get();
        }
      }
      for (int index = 0; index < n; index++){
        // trying to look at one of three digit to sort after.
        int v=1;
        int digit = (q[index]/v)%10;
        v*=10;

        queue[digit].put(q[index]);
      }
      for (int p = 0; p < n; p++){
        while(queue[p].count() != 0) {
          q[p] = (queue[p].get());
        }
      }
    }
  }
}

また、関数に1つのキューを引数として取り、戻ったときにそのキューが昇順になるようにすることもできますか？もしそうなら、どのように？

助けてください。私の英語が下手で、上手くいかない場合は申し訳ありません。

詳細が必要な場合はお知らせください。

import java.util.Random;
public class RadTest extends IntQueue {

    public static void main(String[] args)
    {
        int [] q = new int[10];
        Random r = new Random();
        int t = 0;
        int size = 10;
        while(t != size)
        {
            q[t] = (r.nextInt(1000));
            t++;
        }

        for(int i = 0; i!= size; i++)
        {
            System.out.println(q[i]);
        }

        System.out.println("Radad: \n");
        radixSort(q,size,3);

        for(int i = 0; i!= size; i++)
        {
            System.out.println(q[i]);
        }

    }
}

これがあなたが話していたことだといいのですが...

ご回答ありがとうございます、調査させていただきます。私のために問題を解決する誰かを探していません。ヘルプとアイデアを探しています。どうすれば解決できますか。

私の仕事ではそれは言う：

キューでソートする整数の基数ソート関数を実装します。関数は引数として1つのキューを取り、戻ったときにそのキューに同じ値が昇順で含まれている必要があります。値は0〜999であると想定できます。

100個の整数をキューに入れて基数ソート関数を使用して並べ替えることはできますか？それとも、数値を配列に入れてから、キューを使用する基数ソート関数に配列する必要がありますか？

数値をIntキューに入れ、そのキューを関数に入れる必要があるように理解しましたが、それは機能しませんでした。

しかし、あなたの答えに感謝しますそれらを見て、私の問題を解決しようとします。しかし、あなたが助けることができると思うならば、コメントを残してください。

4

3 に答える 3

1

これは、私が試したテストケースで機能します。完全に文書化されているわけではありませんが、問題ないと思います。それを読んで、あなたが現在行っていることと比較し、哲学においてあなたが持っているものが私のものと異なる理由を見つけてください. 私が「怠惰な」方法で行ったところにマークされている他のこともありますが、より良い方法で行う必要があります。

import java.util.*;
class Radix {

    static int[] radixSort(int[] arr) {
        // Bucket is only used in this method, so I declare it here
        // I'm not 100% sure I recommend doing this in production code
        // but it turns out, it's perfectly legal to do!
        class Bucket {
            private List<Integer> list = new LinkedList<Integer>();
            int[] sorted;

            public void add(int i) { list.add(i);  sorted = null;}

            public int[] getSortedArray() {
                if(sorted == null) {
                    sorted = new int[list.size()];
                    int i = 0;
                    for(Integer val : list) {
                        sorted[i++] = val.intValue(); // probably could autobox, oh well
                    }
                    Arrays.sort(sorted); // use whatever method you want to sort here... 
                                         // Arrays.sort probably isn't allowed
                }
                return sorted;
            }
        }

        int maxLen = 0;
        for(int i : arr) {
            if(i < 0) throw new IllegalArgumentException("I don't deal with negative numbers");
            int len = numKeys(i);
            if(len > maxLen) maxLen = len;
        }

        Bucket[] buckets = new Bucket[maxLen];

        for(int i = 0; i < buckets.length; i++) buckets[i] = new Bucket();
        for(int i : arr) buckets[numKeys(i)-1].add(i);

        int[] result = new int[arr.length];
        int[] posarr = new int[buckets.length]; // all int to 0

        for(int i = 0; i < result.length; i++) {
            // get the 'best' element, which will be the most appropriate from
            // the set of earliest unused elements from each bucket
            int best = -1;
            int bestpos = -1;
            for(int p = 0; p < posarr.length; p++) {
                if(posarr[p] == buckets[p].getSortedArray().length) continue;
                int oldbest = best;
                best = bestOf(best, buckets[p].getSortedArray()[posarr[p]]);
                if(best != oldbest) {
                    bestpos = p;
                }


            }
            posarr[bestpos]++;
            result[i] = best;
        }

        return result;

    }

    static int bestOf(int a, int b) {
        if(a == -1) return b;
        // you'll have to write this yourself :)
        String as = a+"";
        String bs = b+"";
        if(as.compareTo(bs) < 0) return a;
        return b;
    }

    static int numKeys(int i) {
        if(i < 0) throw new IllegalArgumentException("I don't deal with negative numbers");
        if(i == 0) return 1;
        //return (i+"").length(); // lame method :}
        int len = 0;
        while(i > 0) {
            len++;
            i /= 10;
        }
        return len;
    }

    public static void main(String[] args) {

        int[] test = {1, 6, 31, 65, 143, 316, 93, 736};
        int[] res = radixSort(test);
        for(int i : res) System.out.println(i);
    }
}
于 2011-02-17T23:25:02.833 に答える
0

まあ、解決策をほとんど投稿しない限り、私は助けることができないと思います (ヒントを与えるだけではもっと疲れますし、少し疲れています、申し訳ありません)。それはどのように聞こえますか？:-)

何らかのアルゴリズムを実装している場合、優れたファズテスターを考え出すことは常に良い考えです。それが実装の可能性で実行されるかどうか100％の確実性はありませんが、それが機能する可能性があります（基数ソートには奇妙なエッジケースはありませんが、それは非常にまれにしか発生しないことを認識しています）

private static void fuzztest() throws Exception{
    Random rnd = new Random();
    int testcnt = 0;
    final int NR_TESTS = 10000;
    // Maximum size of array.
    final int MAX_DATA_LENGTH = 1000;
    // Maximum value allowed for each integer. 
    final int MAX_SIZE = Integer.MAX_VALUE; 

    while(testcnt < NR_TESTS){
     int len = rnd.nextInt(MAX_DATA_LENGTH) + 1;
     Integer[] array = new Integer[len];
     Integer[] radix = new Integer[len];

     for(int i = 0; i < len; i++){
      array[i] = rnd.nextInt(MAX_SIZE);
      radix[i] = new Integer(array[i]);
     }

     Arrays.sort(array);
     sort(radix);  // use your own sort function here.

     for(int i = 0; i < len; i++){
      if(array[i].compareTo(radix[i]) != 0){
       throw new Exception("Not sorted!");
      }
     }
     System.out.println(testcnt);
     testcnt++;
    }
于 2011-02-18T00:05:09.843 に答える
0

奇妙に見える 1 つのこと:

  for (int p = 0; p < n; p++){
    while(queue[p].count() != 0) {
      q[p] = (queue[p].get());
    }
  }

p は、0 から n-1 の範囲の q のインデックス、または 0 から 9 の範囲のキューのインデックスであると想定されていますか? 両方である可能性は低いです...

別：

  for (int index = 0; index < n; index++){
    // trying to look at one of three digit to sort after.
    int v=1;
    int digit = (q[index]/v)%10;
    v*=10;

    queue[digit].put(q[index]);
  }

v を 10 倍して、次の繰り返しで v = 1 で上書きするのはなぜですか? v は常に 1 であり、反復ごとに同じ数字が表示されることを認識していますか?

于 2011-02-17T23:15:13.667 に答える