バケットのバケットサイズでのバケット

Question

バケットソートのコードを記述しようとしていますが、各バケットのバケットサイズで混乱しています。私のコードは以下の通りです。入力配列：{12,11,13,5,6,7,10,22,4,16,1,26}。

私は各バケットのバケットサイズ> 3を渡していますが、並べ替え順に出力を取得しません。バケツサイズ1と2に最適です。

public void bucsort(int[] arr,int bucketSize){ 

     if(arr.length==0) return; 

     int max=arr[0]; 
     int min=arr[0]; 

     for(int i=0; i<arr.length;i++){ 
      if(arr[i]<min) 
      { 
       min=arr[i]; 
      } 
      else 
       max=arr[i]; 
     } 
     int bucketCount= (max - min)/bucketSize + 1; 
     List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketCount); 
     // int divider= (max+1)/bucketCount; 

     for (int i = 0; i < bucketCount; i++) { 
       buckets.add(new ArrayList<Integer>()); 
      } 
     for (int i = 0; i < arr.length; i++) { 

       buckets.get((arr[i]-min)/bucketSize).add(arr[i]); 
      } 
     int currentIndex = 0; 
      for (int i = 0; i < buckets.size(); i++) { 
       Integer[] bucketArray = new Integer[buckets.get(i).size()]; 
       bucketArray = buckets.get(i).toArray(bucketArray); 
       InsertionSort(bucketArray); 
       for (int j = 0; j < bucketArray.length; j++) { 
        arr[currentIndex++] = bucketArray[j]; 
       } 
      }  
    } 

いいえ、バケツとそのサイズの？

max-min関数のメソッドを編集し、プログラムをデバッグしました。私の挿入中にいくつかの間違いの並べ替え

コードがあるようです：

public void InsertionSort(Integer[] arr){ 


     for(int i=1; i<arr.length; i++){ 
      int value=arr[i]; 
      int hole=i; 

      while(hole>0 && arr[hole-1]>value){ 

       arr[hole]=arr[hole-1]; 

       hole--; 
      } 

      arr[hole-1]=value; 
     } 
    } 

メインFUNC

public static void main(String[] args) { 

     int arr[] = {12, 11, 13, 5, 6, 7,10,22,4,16,1,26}; 

     BucketSort ob = new BucketSort(); 
     ob.bucsort(arr, 5); 
     printArray(arr); 
    } 
    static void printArray(int arr[]) 
    { 
     int n = arr.length; 
     for (int i=0; i<n; ++i) 
      System.out.print(arr[i] + " "); 
     System.out.println(); 
    } 

バケットサイズ5のための私の出力：5 1 4 6 7 10 12 11 13 16 22 26 サイズ3の場合：1 5 4 6 7 12 10 11 13 16 22 26 サイズ2の場合：1 4 5 6 7 10 12 11 13 16 22 26

Answer 1

であなたのInsertionSort方法を

 int value=arr[i]; 
     int hole=i; 

     while(hole>0 && arr[hole]>value){ 

この時点では、arr[hole]は常にvalueに等しくなるため、whileループには絶対に入りません。だから、何もソートされません。小さなバケットサイズの場合は、問題ではないことが幸運かもしれません。バケツサイズ1の場合、それは確かにありません。バケットサイズ2の場合でもソートには1つのエラーがあります。

1 4 5 6 7 10 12 11 13 16 22 26 

12は、同じバケットになり、並べ替えられないため、11より前になります。

私はあなたのコメントからこれを取った：while (hole > 0 && arr[hole - 1] > value) {。あなたのリクエストに応じて、今の方法は、次のようになります。すべてのバケットはそれでも問題が解決しない場合は、我々は同じようにやっていない何かがなければならない1から19までサイズで

public void insertionSort(Integer[] arr) { // renamed to small i since it’s a method 

    for (int i = 1; i < arr.length; i++) { 
     int value = arr[i]; 
     int hole = i; 

     while (hole > 0 && arr[hole - 1] > value) { 

      arr[hole] = arr[hole - 1]; 

      hole--; 
     } 

     arr[hole] = value; 
    } 
} 

は、今私は正しいソートを取得します。

これは脇にありますが、何度か言及したように、コードにはmaxというバグがあります。私は4のmax取得

int arr[] = { 3, 10, 4 }; 

（期待を：：10）私は、この入力を試してみましたが、この行でjava.lang.IndexOutOfBoundsException: Index: 1, Size: 1：

  buckets.get((arr[i]-min)/bucketSize).add(arr[i]); 

Answer 2

max-minが間違っています... （あなたは論理エラー）あなたのコードに

int minValue = array[0]; 
     int maxValue = array[0]; 
     for (int i = 1; i < array.Length; i++) { 
      if (array[i] < minValue) { 
       minValue = array[i]; 
      } else if (array[i] > maxValue) { 
       maxValue = array[i]; 
      } 
     } 

：

 1 4 3 
min 1 1 1 
max 1 4 3 

これが正しいimplemenation

for (i = 1; i < length; i++) { 
      j = i; 
      while (j > 0 && arr[j - 1] > arr[j]) { 
        tmp = arr[j]; 
        arr[j] = arr[j - 1]; 
        arr[j - 1] = tmp; 
        j--; 
      } 
} 

になり、私は時間を得るとき、私はあなたのコードをデバッグします。..