Поразрядная сортировка набора целых чисел. Автоматическое построение логики визуализатора


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

     1. Пройти по массиву A, увеличивая на единицу значение счетчика с индексом d(j,n).
     2. Пройти по массиву counter, записывая в каждую ячейку сумму всех предыдущих элементов этого массива. Эта сумма является количеством чисел исходного массива, которые после сортировки должны будут находиться слева от числа, содержащего в j-ом разряде цифру, равную индексу этого счетчика. Таким образом, мы получили позицию этого числа в результирующем массиве.
     3. Скопировать в массив B значения элементов исходного массива. При этом значение n-го элемента массива A переносится в ячейку с индексом counter[d(j,n)]. Поскольку значения j-го разряда элементов массива A могут повторяться, то после копирования каждого элемента следует увеличить на единицу значение соответствующего счетчика. После заполнения массива B все элементы из него копируются в массив A. После этого происходит переход к следующему значению переменной j.


Автор: А.И. Пономарев. Технология визуализации: Г.А. Корнеев. Руководитель: А.А. Шалыто

Санкт-Петербургский государственный университет информационных технологий, механики и оптики.
Кафедра "Компьютерные технологии"

Copyright 2003 by Anton Ponomarev