Структуры данных и алгоритмы (1021739), страница 63
Текст из файла (страница 63)
В последнем примечании указывалось, что в действительностивремя выполнения цикла в строках (1), (2) имеет порядок О(п). Если надо сделатьтолько k итераций цикла (3) - (5), то на это потратится время порядка O(k logn).Поэтому отбор k минимальных элементов процедура heapsort выполнит за времяпорядка О(п + k logn). Отсюда следует, что при k < n/logn на выполнение этойоперации потребуется время порядка О(п).8.5. „Карманная" сортировкаПравомерен вопрос: всегда ли при сортировке п элементов нижняя граница времени выполнения имеет порядок Й(п logn)? В следующем разделе мы рассмотрим алгоритмы сортировки и их нижнюю границу времени выполнения, если о типе данных ключей не предполагается ничего, кроме того, что их можно упорядочить посредством некой функции, показывающей, когда один ключ "меньше чем" другой.Часто можно получить время сортировки меньшее, чем О(п logn), но необходима дополнительная информация о сортируемых ключах.Пример 8.5.
Предположим, что значения ключей являются целыми числами изинтервала от 1 до п, они не повторяются и число сортируемых элементов также равно п. Если обозначить через А и В массивы типа аггау[1..п] of recordtype, n элементов, подлежащих сортировке, первоначально находятся в массиве А, тогда можно организовать поочередное помещение в массив В записей в порядке возрастания значений ключей следующим образом:for i: = 1 to л doB[A[i].Jcey]:= A[i];(8.9)Этот код вычисляет, где в массиве В должен находиться элемент A[i], и помещаетего туда. Весь этот цикл требует времени порядка О(п) и работает корректно толькотогда, когда значения всех ключей различны и являются целыми числами из интервала от 1 до п.1Более точный анализ показывает, что это время имеет порядок О(п). Для i из интервалаот п/2 до л/4 + 1 из (8.8) следует, что в процедуре pushdown цикл while выполняется не болееодного раза.
Для i из интервала от л/4 до п/8 + 1 выполняются не более двух итераций и т.д.Поэтому общее количество итераций этого цикла для i из интервала от п/2 до 1 ограниченовеличиной 1*п/4 + 2*п/8 + 3*л/16 + .... С другой стороны, эта улучшенная оценка не влияетна время выполнения процедуры heapsort в целом, так как здесь основное время тратится навыполнение строк (3) - (5).8.5. "КАРМАННАЯ" СОРТИРОВКА247Существует другой способ сортировки элементов массива А с временем О(п), нобез использования второго массива В.
Поочередно посетим элементы А[1], .... А[п].Если запись в ячейке A[i] имеет ключ j и j * i, то меняются местами записи в ячейках A[i] и A[j]. Если после этой перестановки новая запись в ячейке A[i] имеет ключk и k Ф i, то осуществляется перестановка между A[i] и A[k] и т.д. Каждая перестановка помещает хотя бы одну запись в нужном порядке. Поэтому данный алгоритмсортировки элементов массива А на месте имеет время выполнения порядка О(п).for i:= 1 to n dowhile A[i].key <> i doswap(A[i], A [ A [ i ] . k e y ] ) ;ППрограмма (8.9) — это простой пример "карманной" сортировки, где создаются"карманы" для хранения записей с определенным значением ключа.
Мы проверяем,имеет ли данная запись ключ со значением г, и если это так, то помещаем эту записьв "карман" для записей, чьи значения ключей равны г. В программе (8.9)"карманами" являются элементы массива В, где B\i\ — "карман" для записей с ключевым значением i. Массив в качестве "карманов" можно использовать только в простейшем случае, когда мы знаем, что не может быть более одной записи в одном"кармане".
Более того, при использовании массива в качестве "карманов" не возникает необходимости в упорядочивании элементов внутри "кармана", так как в одном"кармане" содержится не более одной записи, а алгоритм построен так, чтобы элементы в массиве располагались в правильном порядке.Но в общем случае мы должны быть готовы к тому, что в одном "кармане" можетхраниться несколько записей, а также должны уметь объединять содержимое нескольких "карманов" в один, располагая элементы в объединенном "кармане" в правильном порядке. Для определенности далее будем считать, что элементы массива Аимеют тип данных recordtype, а ключи записей — тип keytype. Кроме того, примем,но только в этом разделе, что тип данных keytype является перечислимым типом,т.е. таким, как последовательность целых чисел 1, 2, ..., п, или как символьныестроки.
Обозначим через listtype (тип списка) тип данных, который представляетсписки элементов типа recordtype. Тип listtype может быть любым типом списков,описанным в главе 2, но в данном случае нам наиболее подходят связанные списки,поскольку мы будем их наращивать в "карманах" до размеров, которые нельзя предусмотреть заранее. Можно только предвидеть, что общая длина всех списков фиксирована и равна п, поэтому при необходимости массив из п ячеек может обеспечитьреализацию списков для всех "карманов".Необходим также массив В типа arrayfkeytype] of listtype.
Это будет массив"карманов", хранящих списки (или заголовки списков, если используются связанныесписки). Индексы массива В имеют тип данных keytype, так что каждая ячейка этого массива соответствует одному значению ключа. Таким образом, мы уже можемобобщить программу (8.9), поскольку теперь "карманы" имеют достаточную емкость.Рассмотрим, как можно выполнить объединение "карманов". Формально над списками <*!, а2, ..., а,- и Ъ\, Ь2, ..., Ь, надо выполнить операцию конкатенации списков, врезультате которой получим список аг, а2а,-, Ь\, Ь2, ....
Ъ-г Для реализации оператора конкатенации CONCATENATED, L2), который заменяет список L\ объединенным списком LiZ/2, можно использовать любые представления списков, которые мыизучали в главе 2.Для более эффективного выполнения оператора конкатенации в добавление к заголовкам списков можно использовать указатели на последние элементы списков(или на заголовок списка, если список пустой). Такое нововведение позволит избежать просмотра всех элементов списка для нахождения последнего. На рис. 8.4 пунктирными линиями показаны измененные указатели при конкатенации списков L\ и L2в один общий список LJ. Список L2 после объединения списков предполагается"уничтоженным", поэтому указатели на его заголовок и конец "обнуляются".248ГЛАВА 8.
СОРТИРОВКАЗаголовок1Конец L1Заголовок L,\Конец L2Рис. 8.4. Конкатенация связанных списковТеперь можно написать программу "карманной" сортировки записей, когда полеключей является перечислимым типом. Эта программа, показанная в листинге 8.12,написана с использованием базовых операторов, выполняемых над списками. Какуже говорилось, связанные списки являются предпочтительной реализацией"карманов", но, конечно, можно использовать и другие реализации.
Напомним также, что в соответствии с нашими предположениями, массив А типа аггау[1..п] of recodrtype содержит элементы, подлежащие сортировке, а массив В типа агray[keytype] of listtype предназначен для "карманов". Будем также считать, что переменные перечислительного типа keytype могут изменяться в пределах от lowkey(нижний ключ) до highkey (верхний ключ)..:Листинг 8.12. Программа й/nsorf („карманная" сортировка)1" : : : .:.(1)(2)(3)(4).•:•'••. • ' • : ' . .'•.:'.'' ."'.•;••'.' •''::.•'•'.:. •.
.•-.--.~..v.;..:•...procedure binsort;{ Сортирует элементы массива А, помещая отсортированныйсписок в "карман" В[lowkey] }vari: integer;v: keytype;begin{ начинается занесение записей в "карманы" }for i:= 1 to n do{ помещение элемента A[i] в начало "кармана",соответствующего ключу этого элемента }INSERT(Л[i], FIRST(B[A[i].fcey]), B[A[i].key]);for v.= succ(lowkey) to highkey do{конкатенация всех "карманов" в конец "кармана" B[lowkey]}CONCATENATE(В[lowkey}, В[v])end; { binsort }Анализ „карманной" сортировкиЕсли сортируется п элементов, которые имеют /га различных значений ключей(следовательно, т различных "карманов"), тогда программа из листинга 8.12 выполняется за время порядка О(п + т), если, конечно, используется подходящая струк1Для читателя, незнакомого с языком Pascal (или мало знакомого с этим языком), поясним, что применяемая в этом листинге стандартная функция Pascal succ(x) для данных перечислимого типа возвращает следующее за х значение.
— Прим. ред.8.5. "КАРМАННАЯ" СОРТИРОВКА249тура данных. В частности, если т < п, то сортировка выполняется за время О(п). Вкачестве "подходящей" структуры данных мы считаем связанные списки. Указателина концы списков, показанные на рис. 8.4, полезны, но не обязательны.Цикл в строках (1), (2) листинга 8.12, помещающие записи в "карманы", выполняется за время порядка О(п), поскольку оператор INSERT в строке (2) требуетфиксированного времени, так как вставка записей всегда осуществляется в началосписков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
