|
Сортировка подсчетом позволяет отсортировать за линейное время последовательность, в которой каждый элемент - целое положительное число в известном диапазоне (не превосходящее заранее известного k). В реализации визуализатора k равно десяти. Идея алгоритма состоит в том, чтобы для каждого элемента x предварительно подсчитать, сколько элементов входной последовательности меньше x. После этого х записывается напрямую в выходной массив в соответствии с этим числом. Например, если семнадцать элементов входного массива меньше х, то в выходном массиве х должен быть записан на место с номером восемнадцать. Используются следующие обозначения: A[1..n] - входная последовательность; C[1..k] - вспомогательный массив из k элементов; B[1..n] - выходная отсортированная последовательность. Работа алгоритма заключается в следующем. В элемент C[i] заносится количество элементов массива A, равных i. Затем находятся частичные суммы последовательности C[1], C[2], ..., C[k], каждая из которых является количеством элементов, не превосходящих i. После этого каждый элемент A[i] из входного массива помещается в выходной массив B на позицию, равную значению элемента С[A[i]]. |
Copyright 2004 by Vladimir Dobrovolski