Основной особенностью данного алгоритма является то, что вместо непосредственного сравнения элементов, производится разделение значения на части - разряды ключа. До сортировки необходимо знать два параметра: k и m, где k - количество разрядов в самом длинном ключе, а m - разрядность данных (количество возможных значений разряда ключа). В представленном визуализаторе количество разрядов ограничено четырьмя, а m равно десяти, поскольку рассматриваются десятичные числа. Предположим, что элементы массива A (отображается в верхнем ряду визуализатора) есть k-разрядные десятичные числа, разрядность максимального числа известна заранее. Обозначим d(j,n) - j-ю справа цифра числа n. Пусть B (отображается в нижнем ряду визуализатора) - вспомогательный массив, вначале пустой, а counter (отображается в среднем ряду визуализатора) – массив счетчиков из m элементов, заполненный нулями. Для каждого j = 1, 2,..., k необходимо: | |
1. Пройти по массиву A, увеличивая на единицу значение счетчика с индексом d(j,n). |
Copyright 2003 by Anton Ponomarev