Почему моя программа сортировки так медленно? (сортировка по методу radix/bucket в java)

Question

Это гибридный гибридный гибрид, который жестко закодирован для 9-значных чисел. Моя программа быстрой сортировки более чем вдвое быстрее, чем сортировать 10-миллиметровые числа. Я проверял, что результат правильный, он просто медленный.

Код:

public static void main(String[] args) { 
    Scanner in = new Scanner(System.in); 
    ArrayList<Integer> inputs = new ArrayList<>(); 
    while (in.hasNext()) { 
     inputs.add(in.nextInt()); 
    } 
    radixSort(inputs); 
    //System.out.print(toString(radixSort(inputs))); 
} 

public static ArrayList<Integer> radixSort(ArrayList<Integer> a) { 
    for (int i = 1; i <= 9; i++) { 
     a = bucketSort(a, i); 
    } 
    return a; 
} 

public static ArrayList<Integer> bucketSort(ArrayList<Integer> a, int index) { 
    // Creates buckets 
    ArrayList<ArrayList<Integer>> b = new ArrayList<ArrayList<Integer>>(); 
    for (int i = 0; i < 10; i++) { 
     b.add(new ArrayList<Integer>()); 
    } 
    // Sorts into buckets 
    for (int i = 0; i < a.size(); i++) { 
     b.get(key(a.get(i), index)).add(a.get(i)); 
    } 
    // Concatenates buckets 
    ArrayList<Integer> c = new ArrayList<>(); 
    for (int i = 0; i < b.size(); i++) { 
     c.addAll(b.get(i)); 
    } 
    return c; 
} 

// Takes an integer and index and returns digit at index 
public static int key(int num, int ind) { 
    int digit = num/(int)Math.pow(10, ind - 1); 
    digit = digit % 10; 
    return (int)digit; 
} 

public static String toString(ArrayList<Integer> a){ 
    StringBuilder s = new StringBuilder(); 
    for (int i = 0; i < a.size(); i++){ 
     s.append(String.format("%09d\n", a.get(i))); 
    } 
    return s.toString(); 
} 

Answer 1

Основная причина медленности является добавлением одно целого числа в то время, в каждый массив ковша, имеющей снова приложить для того, чтобы сцепить ведра, которые включают динамически расширяющиеся массивы.

Сводная вариация сортировки первого разряда младшего значащего разряда делает однократное распределение второго массива того же размера, что и исходный массив. Для 9-значного примера он может генерировать подсчеты для количества вхождений «0», «1», «9», для каждой цифры, затем конвертировать отсчеты в начальные индексы для начала каждого размера переменной ковша, устраняя необходимость конкатенации. Для 9-значного примера матрица [9] [10] может использоваться для подсчетов/индексов, поэтому для генерации матрицы будет использоваться только один проход.

вики статья:

http://en.wikipedia.org/wiki/Counting_sort

Пример C++ код, который сортирует массив 32 битовых целых чисел без знака с использованием байта размера "цифры", так что матрица импульсов/индексов [4] [256]. Единственная часть C++ - это std :: swap(), иначе это код C.

typedef unsigned int uint32_t; 

// a is input array, b is working array 
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // count/index matrix 
size_t i,j,m,n; 
uint32_t u; 
    for(i = 0; i < count; i++){   // generate histograms 
     u = a[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     m = 0; 
     for(i = 0; i < 256; i++){ 
      n = mIndex[j][i]; 
      mIndex[j][i] = m; 
      m += n; 
     }  
    } 
    for(j = 0; j < 4; j++){    // radix sort 
     for(i = 0; i < count; i++){  // sort by current lsb 
      u = a[i]; 
      m = (size_t)(u>>(j<<3))&0xff; 
      b[mIndex[j][m]++] = u; 
     } 
     std::swap(a, b);    // swap ptrs 
    } 
    return(a); 
}