Radix Sort: что означает «группы» в сортировке radix?

Question

У меня есть сортировка алгоритма для моего класса cs. Мне нужно преобразовать псевдокод Radix Sort в C++. Вот мой псевдокод:

radixSort(int theArray[], in n:integer, in d:integer) 
// sort n d-digit integers in the array theArray 
    for (j=d down to 1) { 
     Initialize 10 groups to empty 
     Initialize a counter for each group to 0 
     for (i=0 through n-1) { 
       k = jth digit of theArray[i] 
       Place theArray[i] at the end of group k 
       Increase kth counter by 1 
     } 
     Replace the items in theArray with all the items in 
     group 0, followed by all the items in group 1, and so on. 
    } 

Проблема в том, что я действительно не понимаю, что означает «группы». Сначала я пытаюсь сделать массив, но, конечно, он переопределяет числа. Как я могу группировать числа в соответствии с их последней цифрой? Я не прошу ни о каком коде. Мне просто нужно понять. Большое спасибо.

Answer 1

Возьмите каждое число, разделите на 10 в степени х, с х быть на каждой итерации цикла, то это число мод на 10.

(num/10**x) % 10 

Это даст вам значащей цифры на первый проход, затем перейдите к каждой цифре в порядке справа налево. Количество итераций должно быть равно длине наибольшего числа.