RadixSort Algorithmus Laufzeit

Question

So habe ich eine Zuordnung, wo ich verschiedene Sortieralgorithmen auf eine große Anzahl von zufällig generierten Listen ausführen müssen. Dann muss ich einen Bericht vorlegen, der die Laufzeiten der verschiedenen Algorithmen vergleicht. Ich habe bisher den Code von 3 Sortieralgorithmen geschrieben: Quicksort, Mergesort und Heapsort. Ich habe nur Radixsort übrig. Unten ist der Code. Dieser Code wirft mir eine ArrayIndexOutOfBoundsException auf dieser Linie:

b[--bucket[(a[i]/exp) % 10]] = a[i]; 

aber ich kann nicht ganz herausfinden, wie Sie den Code zu ändern, um es richtig zu machen.

import java.util.*; 


public class RadixSort { 

    public static void main(String[] args) { 
     Random generator = new Random(System.currentTimeMillis()); 
     Scanner scan = new Scanner(System.in); 
     int size = scan.nextInt(); 
     int[] x = new int[size]; 

     long start = System.currentTimeMillis(); 

     for (int i = 0; i < size; i++) 
      x[i] = getRandomNumberInRange(0, 100); 

     radixSort(x); 
     System.out.println(Arrays.toString(x)); 
     long runtime = System.currentTimeMillis() - start; 
     System.out.println("Runtime: " + runtime); 
    }  

    private static int getRandomNumberInRange(int min, int max) { 
     if (min >= max) 
      throw new IllegalArgumentException("max must be greater than min"); 

     return (int)(Math.random() * ((max - min) + 1)) + min; 
    } 

    public static void radixSort(int[] a) { 
     int i, m = a[0], exp = 1, n = a.length; 
     int[] b = new int[10]; 

     for (i = 1; i < n; i++) 
      if (a[i] > m) 
       m = a[i]; 

     while (m/exp > 0) { 
      int[] bucket = new int[10]; 

      for (i = 0; i < n; i++) 
       bucket[(a[i]/exp) % 10]++; 
      for (i = 1; i < 10; i++) 
       bucket[i] += bucket[i - 1]; 
      for (i = n - 1; i >= 0; i--) 
       b[--bucket[(a[i]/exp) % 10]] = a[i]; 
      for (i = 0; i < n; i++) 
       a[i] = b[i]; 
      exp *= 10;   
     } 
    }  
} 

Answer 1

Es geschieht, weil Sie explizit die feste Größe von int[] b Array definiert haben:

int[] b = new int[10]; 

, dass der Grund ist es für den Fall, läuft der Eingang größer als 10 ist.

Ändern Sie die Variable von einem Parameter in die variable Länge des Arrays.

int[] b = new int[a.length]; 

Außerdem empfehlen Sie mich (0; n> die immer von Input für Zahlen nur im Intervall zu beheben.