Время выполнения алгоритма RadixSort

Question

Итак, у меня есть назначение, где мне нужно запускать различные алгоритмы сортировки на большом количестве произвольно сгенерированных списков. Затем я должен представить отчет, сравнивающий время работы различных алгоритмов. Я написал код из 3 алгоритмов сортировки: quicksort, mergesort и heapsort. У меня осталось только радиус. Ниже приведен код. Этот код бросает мне ArrayIndexOutOfBoundsException на этой линии:

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

, но я не могу вполне понять, как изменить код, чтобы сделать это правильно.

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

Это происходит потому, что вы явно определили фиксированный размер массива int[] b:

int[] b = new int[10]; 

Вот причине переполнения в случае ввода больше, чем 10.

Измените его на переменную длину массива из параметра.

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

Кроме того, я рекомендую вам зафиксировать получение исходных данных для чисел только в интервале (0; n>.