Структуры данных и алгоритмы (1021739), страница 58
Текст из файла (страница 58)
Мы можем постулировать существование константы - °о типаkeytype, которая будет меньше значения ключа любой записи, встречающейся напрактике. Если такую константу нельзя применить, то при вставке A[i] в позицию/' - 1 надо проверить, не будет ли /' = 1, если нет, тогда сравнивать элемент A[i](который сейчас находится в позиции ;') с элементом А[у - 1]. Описанный алгоритмпоказан в листинге 8.3..:•.•-,•!.;••:.;';'.• •;•-.'•:..•''"-:fKfHSM:jfitSiЛистинг 8.3. Сортировка вставками(1)(2)(3)(4)•/Щ',,,,„.,.„А[0] .key.= - °°;for i:= 2 to л do beginj:= i;while A[j] < A[j - I] do begin(5)swapUtj], A t j - 1]);(6)endendj:= j - IПример 8.2.
В табл. 8.3 показан начальный список из табл. 8.1 и последовательные этапы алгоритма вставкой для 1 = 2, 3, ..., 6. После каждого этапа алгоритма элементы, расположенные выше линии, уже упорядочены, хотя между нимина последующих этапах могут быть вставлены элементы, которые сейчас находятся ниже линии. D,,..:: ;'. :.- i. .
. ..' . - . .;.'"Таблица 8.3. Этапы сортировки вставками— оо— оо— оо— 00— 00— 00ПилиПилиКракатауАгунгАгунгАгунгЭтнаЭтнаПилиКракатауКракатауВезувийКракатауКракатауЭтнаПилиПилиКракатауСв. ЕленаПилиСв. ЕленаАгунгАгунгАгунгЭтнаСв. ЕлеяаСв. ЕленаСв. ЕленаСв. ЕленаЭтнаВезувийВезувийВезувийВезувийВезувийЭтна•Начальное положениеi=2i=38.2. ПРОСТЫЕ СХЕМЫ СОРТИРОВКИi=4i=5i=6 ,Сортировка посредством выбораИдея сортировки посредством выбора также элементарна, как и те два методасортировки, которые мы уже рассмотрели. На i-м этапе сортировки выбирается запись с наименьшим ключом среди записей A[i], .... А[п] и меняется местами с записью A[i].
В результате после i-ro этапа все записи А[1], .... A[i] будут упорядочены.Сортировку посредством выбора можно описать следующим образом:for i : = l t o n - l d oвыбрать среди А[1], ..., А [л] элемент с наименьшим ключом ипоменять его местами с А[1];Более полный код, реализующий этот метод сортировки, приведен в листинге 8.4.Листинг 8.4. Сортировка посредством выбораvar(1)(2)(3)(4)(5)(6)(7)lowkey: keytype; { текущий наименьший ключ, найденныйпри проходе по элементам A[i], ..., А[п] }lowindex: integer; { позиция элемента с ключом lowkey }beginfor i:= 1 to л - 1 do beginlowindex:= i;lowkey:= A[i].key;for j:= i + 1 to л do{ сравнение ключей с текущим ключом lowkey }if A[j].key < lowkey then beginlowkey:= A[j].key;lowindex:= jend;swap(A[i], A[lowindex])(8)end;endПример 8.З.
В табл. 8.4 показаны этапы сортировки посредством выбора для списка из табл. 8.1. Например, на 1-м этапе значение lowindex равно 4, т.е. позицииАгунга, который меняется с Пили, элементом Л[1].Линии в табл. 8.4 показывают, что элементы, расположенные выше ее, имеютнаименьшие значения ключей и уже упорядочены. После (п - 1)-го этапа элементА[п] также стоит на "правильном" месте, так как выше его все записи имеют меньшие значения ключей.
DТаблица 8.4. Сортировка посредством выбораПилиЭтнаКракатауАгунгСв. ЕленаВезувийАгунгЭтнаКракатауПилиСв. ЕленаВезувийНачальное положение 1-й этап282АгунгВезувийКракатауПилиСв. ЕленаЭтнаАгунгВезувийКракатауПилиСв. ЕленаЭтнаАгунгВезувийКракатауПилиСв. ЕленаЭтнаАгунгВезувийКракатауПилиСв. ЕленаЭтна2-й этап3-й этап4-й этап5-й этапГЛАВА 8. СОРТИРОВКАВременная сложность методов сортировкиМетоды "пузырька", вставками и посредством выбора имеют временную сложность22О(п ) и £2(п ) на последовательностях из п элементов. Рассмотрим метод "пузырька"(листинг 8.1).
Независимо от того, что подразумевается под типом recordtype, выполнение процедуры swap требует фиксированного времени. Поэтому строки (3), (4) затрачивают Ci единиц времени; с\ — некоторая константа. Следовательно, для фиксированного значения i цикл строк (2) - (4) требует не больше сг(п - i) шагов; с2 — константа.Последняя константа несколько больше константы CL если учитывать операции с индексом j в строке (2). Поэтому вся программа требуетte}1'1зп + 2Х(П - 0 = -С2Л2 + (С3 - -С2)П<=1**сшагов, где слагаемое с3п учитывает операции с индексом i в строке (1). Последнее2выражение не превосходит (с2/2 + с3)п для п > 1, поэтому алгоритм "пузырька"2имеет временную сложность О(п ). Нижняя временная граница для алгоритма равна2£2(л ), поскольку если даже не выполнять процедуру swap (например, если списокуже отсортирован), то все равно п(п — 1)/2 раз выполняется проверка в строке (3).Далее рассмотрим сортировку вставками (листинг 8.3).
Цикл while в строках (4) - (6)выполняется не более O(i) раз, поскольку начальное значение у равно i, а затем jуменьшается на 1 при каждом выполнении этого цикла. Следовательно, цикл forстрок (2) - (6) потребует не более c£*=1i шагов для некоторой константы с. Эта сум2ма имеет порядок О(п ).Читатель может проверить, что если список записей первоначально был отсортирован в обратном порядке, то цикл while в строках (4) - (6) выполняется ровно i - 1раз, поэтому строка (4) выполняется £"_2(*-1) =га п( ~1)/2 раз.
Следовательно, сор2тировка вставками в самом худшем случае требует времени не менее ii(n ). Можнопоказать, что нижняя граница в среднем будет такой же.Наконец, рассмотрим сортировку посредством выбора, показанную в листинге 8.4. Легко проверить, что внутренний цикл в строках (4) - (7) требует времени порядка О(п - i), поскольку j здесь изменяется от i + 1 до и. Поэтому общее время выполнения алгоритма составляет с]£"~ (п - i) для некоторой константы с. Эта сумма,равная сп(п - 1)/2, имеет порядок роста О(л2).
С другой стороны, нетрудно показать,что строка (4) выполняется не менее J^.j X"-m ^ = п^п "" 1) / 2 Раз независимо от начального списка сортируемых элементов. Поэтому сортировка посредством выборатребует времени не менее П(га2) в худшем случае и в среднем.Подсчет перестановокЕсли размер записей большой, тогда процедура swap для перестановки записей,которая присутствует во всех трех вышеописанных алгоритмах, занимает большевремени, чем все другие операции, выполняемые в программе (например, такие каксравнение ключей или вычисление индексов массива).
Поэтому, хотя мы уже показали, что время работы всех трех алгоритмов пропорционально п2, необходимо болеедетально сравнить их с учетом использования процедуры swap.Сначала рассмотрим алгоритм "пузырька". В этом алгоритме процедура swap выполняется (см. листинг 8.1, строка (4)) не менее ^,",1^",^1W = п(п-1)/2 раз, т.е.почти л 2 /2 раз. Но поскольку строка (4) выполняется после условного оператора встроке (3), то можно ожидать, что число перестановок значительно меньше, чем п2/2.В самом деле, в среднем перестановки выполняются только в половине из всехвозможных случаев.
Следовательно, ожидаемое число перестановок, если все воз8.2. ПРОСТЫЕ СХЕМЫ СОРТИРОВКИ233можные исходные последовательности ключей равновероятны, составляет примернои2/4. Для доказательства этого утверждения рассмотрим два списка ключей, которыеобратны друг другу: Ь\ «= Л1( kz, .... ka и L 2 = kn, ftB_i, ..., fej. Переставляются ключиkt и ^ из одного списка, если они расположены в "неправильном" порядке, т.е. нарушают отношение линейного порядка, заданного на множестве значений ключей.Такая перестановка для ключей kt и kt выполняется только один раз, так как онирасположены неправильно или только в списке L b или только в списке L2, но не вобоих сразу.
Поэтому общее число перестановок в алгоритме "пузырька", примененном к спискам LI и L2, равно числу пар элементов, т.е. числу сочетаний из п по 2:С* = п(п -1)/2 . Следовательно, среднее число перестановок для списков Ьг и L2 равно п(п - 1)/4 или примерно п2/4. Поскольку для любого упорядочивания ключейсуществует обратное к нему, как в случае списков L t и L2, то отсюда вытекает, чтосреднее число перестановок для любого списка также равно примерно п2/4.Число перестановок для сортировки вставками в среднем точно такое же, как идля алгоритма "пузырька". Для доказательства этого достаточно применить тот жесамый аргумент: каждая пара элементов подвергается перестановке или в самомупорядочиваемом списке L и в обратном к нему, но никогда в обоих.Если на выполнение процедуры swap необходимы большие вычислительные иливременные ресурсы, то легко увидеть, что в этом случае сортировка посредством выбораболее предпочтительна, нежели другие рассмотренные методы сортировки.
В самом деле, в алгоритме этого метода (листинг 8.4) процедура swap выполняется вне внутреннего цикла, поэтому она выполняется точно п - 1 раз для массива длиной п. Другимисловами, в этом алгоритме осуществляется О(п) перестановок в отличие от двух другихалгоритмов, где количество таких перестановок имеет порядок О(и2). Причина этогопонятна: в методе сортировки посредством выбора элементы "перескакивают" черезбольшой ряд других элементов, вместо того чтобы последовательно меняться с нимиместами, как это делается в алгоритме "пузырька" и алгоритме сортировки вставками.В общем случае, если необходимо упорядочить длинные записи (поэтому их перестановки занимают много времени), целесообразно работать не с массивом записей, ас массивом указателей на записи, используя для сортировки любой подходящий алгоритм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
