| Выше было показано, как следует использовать так называемые универсальные алгоритмы сортировки, пригодные для любого вида данных, подлежащих сравнению. Однако, зачастую информация о множестве значений, которые могут принимать элементы массива, может в корне изменить подход к сортировке. Пусть, например, требуется отсортировать 100000 цифр, вводимых, например, из стандартного потока ввода (это типичная задача для районных или городских олимпиад по информатике). Как уже говорилось в лекции 3, максимальный размер массива даже однобайтовых элементов не может превышать 64 килобайта. Кроме того, время работы любого из универсальных “эффективных” (то есть выполняющих порядка Nlog2N действий) для 100000 элементов скорее всего будет превышать допустимое по условию время решения задачи. Поэтому обратим внимание на то, что элементами массива, подлежащего сортировке, являются не произвольные числа, а цифры, то есть целые числа от 0 до 9. В этом случае алгоритм сортировки фактически заключается в подсчете количества каждой из цифр и записи результата согласно полученным результатам подсчета. Реализовать этот алгоритм можно так: var d:array[0..9] of longint; {массив для подсчета} a:byte;{переменная для ввода цифр} n,i,j:longint; begin read(n);{n - количество цифр} fillchar(d,sizeof(d),0); for i := 1 to n do
begin
read(a); d[a] := d[a] + 1
end;
for j := 0 to 9 do {печатаем результат} for i := 1 to d[j] do write(j:2) end.
Заметим, что эта программа работает верно и в случае, когда какой либо из цифр во вводимой последовательности нет совсем. Подобный алгоритм называют сортировкой подсчетом или “карманной” сортировкой [1, 5]. Его трудоемкость составляет O(N+m) (а именно, 2N + m операций), где m — количество различных элементов в массиве. Очевидно, что если M<=N и мы можем отвести память для подсчета количества каждого из m возможных значений для элементов массива, то алгоритм окажется линейным относительно N. Если же m<N, то алгоритм может как выигрывать, так и проигрывать по сравнению с универсальными эффективными алгоритмами. Например, для массива из 1000 положительных чисел типа integer сортировка подсчетом выполняется за 32767*2 + 1000 = 66534 операции, а, например, сортировка слиянием, — за 2*1000*[log21000]=20000 операций. Но уже для 10000 таких же чисел сортировка подсчетом выполняется за 75534 операции, а слиянием — за 280000.
В качестве упражнения, иллюстрирующего ту же самую идею, что и сортировка подсчетом, реализуйте программу, определяющую, какая буква встречается в тексте чаще всего. Напоминаем, что в Турбо Паскале индексами массива могут служить и символы, в данном случае это можно использовать при описании дополнительного массива. Не забудьте также, что одной и той же букве алфавита соответствуют 2 различных символа, что следует учесть при подсчете (а для русских букв это не настолько просто как для латинских).
Идею сортировки подсчетом продолжает “цифровая” сортировка, объектами которой могут служить произвольные числа и даже строки. Такой алгоритм ранее использовался для сортировки перфокарт [5]. В перфокартах цифры кодировались одиночными дырками в строках 0-9 соответствующей колонки. Сортировочной машине указывали столбец для сортировки и она раскладывала перфокарты на 10 стопок в зависимости от того, какая из дырок была пробита. Как же с помощью этой машины можно было отсортировать колоду перфокарт с многозначными цифрами? Как ни странно, процедуру сортировки начинали не со старшего разряда, а с младшего. Полученные в результате первой сортировки 10 стопок вновь складывали в одну колоду (начиная с нулей в младшем разряде и заканчивая девятками) и сортировали уже по разряду десятков и т.д. Если числа являлись k-значными, то после k операций поразрядной сортировки колода оказывалась упорядоченной. Продемонстрируем это на примере трехзначных чисел (каждый столбец, начиная со второго, показывает результат сортировки исходного столбца по очередному разряду):
Когда числа сортируются по какому-либо разряду важно, чтобы применяемый при этом алгоритм сортировки был устойчивым, то есть числа, у которых в текущем разряде стоят одни и те же цифры, сохраняли то же взаимное расположение, какое было между ними перед сортировкой по этому разряду. Устойчивым является, например, модифицированный алгоритм сортировки подсчетом, в котором в элементе вспомогательного массива d[х] будет храниться количество элементов в массиве, не превосходящих х. Покажем, как изменится при этом программа сортировки массива цифр, расположенных в переменной a типа list (результат поместим в массив b того же типа):
fillchar(d,sizeof(d),0);
for i := 1 to n do
d[a[i]] := d[a[i]] + 1;
for j := 1 to 9 do
d[j] := d[j] + d[j-1];
{d[j] – количество элементов не превосходящих j}
for i := n downto 1 do
begin
b[d[a[i]]] := a[i];
d[a[i]] := d[a[i]]-1
end
В самом деле, в отсортированном массиве a[i] заведомо может стоять на месте d[a[i]], ведь именно столько элементов в массиве не превосходят a[i]. Затем d[a[i]] уменьшается на единицу и другие элементы массива, равные a[i], будут записаны левее. Взаимный порядок между равными элементами при этом не нарушится, так как при записи результата массив просматривается с конца.
Оценим время работы алгоритма цифровой сортировки, с поразрядным использованием сортировки подсчетом. Для N чисел с k знаками (или для строк длины k), в записи которых участвуют m различных чисел (симоволов), количество операций имеет порядок O(kN + km). Если k фиксировано, то общее количество действий имеет порядок O(N). Как и ранее коэффициент в таком линейном алгоритме следует сравнивать со значением log2N, для определения области его эффективного применения. Однако цифровая сортировка совершенно незаменима для упорядочения массивов данных, имеющих несколько различных полей.
|
Главная
Каталог файлов
