Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 15
Текст из файла (страница 15)
Сортировка лап«ивов 8! а не числа необходимых пересылок. В действительности поскольку пересылка элементов, т. е. ключей и сопутствующей информации, обычно требует значительно больше времени, чем сравнение двух ключей, то это улучшение ни в коей мерв не является решающим: важный показатель М по-прежнему остается порядка и'. И в самом деле, пересортировка уже рассортированного массива занимает болыпе времени, чем при сортировке простыми включениями с последовательным поиском! Этот пример показывает, что «очевидное улучшение» часто оказывается намного менее существенным, чем кажется вначале, и в некоторых случаях (которые действительно встречаются! может на самом деле оказаться ухудшением.
В конечном счете сортировка включениями оказывается не очень подходящим методом для цифровых вычислительных машин: включение элемента с последующим сдвигом всего ряда элементов на одну позицию неэкономна. Лучших результатов можно ожидать от метода, при котором пересылки элементов выполняются только для отдельных элементов и на болыпие расстояния. Эта мысль приводит к сортировке выбором, 2 2.2. Сортировка простым выбором Этот метод основан на следующем правиле; !.
Выбирается элемент с наименьшим ключом. 2. Он меняется местами с первым элементом а>, Эти операции затем повторяются с оставшимися п — ! элементами, затем с п — 2 элементами, пока не останется только один элемент — нанболыпий. Этот метод продемонстрирован на тех же восьми ключах в табл. 2.2. Таблица 2.9. Пример сортировки простым амбаром Латал»л>л> квола 06 06 06 06 06 06 06 94 16 06 67 94 19 44 Ш 94 19 44 67 94 55 44 67 44 65 94 67 44 55 67 94 65 12 12 55 12 12 >а 12 >а 12 18 12 16 42 42 42 42 42 42 42 Программу можно представить следующим образом: Мог!:= ! 10 и — ! >!о Ьейт!и «присвоить Й индекс наименыпего элемента из а[>1...
... и!н!»; «поменять местами и, н аа» еп>! 2. Сортировка 3тот метод, называемый сортировкой простым выбором, в неютором смысле противоположен сортировке простыми вклю>ениями; при сортировке простыми включениями на каждом ваге рассматривается только один очередной элемент вход>ой последовательности и все элементы готового массива для >ахождения места включения; при сортировке простым выбо. >ом рассматриваются все элементы входного массива для >ахождения элемента с наименьшим ключом, и этот один >чередной элемент отправляется в готовую последователь>ость. Весь алгоритм сортировки простым выбором пред>тавлен в виде программы 2.3. ргосейпте ггга>ай!ге!ест>оп; тат Ц,7с: >пдех; х: (лет; Ьей!п Гог >':= 1 !о п — 1 да Ьерп/с:= >; х:= а!!); Гот,~:=, >+1 то и йо ИаК.кеу < х.йеу тйеа Ьей!ай:= >; х:= а(Я евб; аЩ;= а(>1; аИ:= х; епй евй Программа 2.3.
Сортировка простым выбором. Анализ сортировки простым выбором. Очевидно, что число " сравнений ключей не зависит от начального порядка ключей. В этом смысле можно сказать, что сортировка простым выбором ведет себя менее естественно, чем сортировка простыми включениями. Мы получаем С = —,' (ла — л). Минна>альиое число пересылок равно М >„=3(л — 1) (2.6) в случае изначально упорядоченных ключей и принимает наи- большее значение: М„„„= !гипс ( — ) + 3 (л — !), если вначале ключи расположены в обратном порядке.
Среднее Мга трудно определить, несмотря на простоту алгоритма. Опо зависит от того, сколько раз определяется, что и> меньше всех предшествуюших величин й>, ..., и, > при просмотре последовательности чисел >г>, ..., й„, Это значение, взятое 2Х Сортировка массивов 83 в среднем для всех перестановок и ключей, число которых равно а1, есть Нл где Н,— л-е гармоническое число Н =1+ — + — +... + — „ ! 1 1 2 3 (см. Д. Кнут, т, 1). Число Н, можно выразить как Н„=1пп+у+ — „— —,„, + ..
„ ! ! где у = 0.577216... — эйлерова константа. Для достаточно больших а мы можем опустить дробные слагаемые и, таким образом, аппроксимировать среднее число присваиваний на 1-м проходе следуюшим образом; Г! = 1п 7+ у+ 1. Тогда среднее число пересылок М,р, при сортировке выбором есть сумма Рь где ! принимает значения от 1 до кс М,, = Е г = а (у + 1) + Е 1п !.
Аппроксимируя далее сумму отдельных слагаемых с помощью интеграла 1и х Их = х (1п х — 1) ~, = п 1п и — и + 1, 1 получаем приближенное значение М„, и(!и и+ у). (2.0) Иы можем сделать вывод, что обычно алгоритм сортировки простым выбором предпочтительней алгоритма сортировки простыми включениями, хотя в случае, когда ключи заранее рассортированы нли почти рассортированы, сортировка простыми включениями все же работает несколько быстрее. 2.2.3. Сортировка простым обменом Классификация методов сортировки не всегда четко определена.
Оба представленных ранее метода можно рассматривать как сортировку обменом. Однако в этом разделе мы остановимся на методе, в котором обмен двух элементов является основной характеристикой процесса. Приведенный ниже алгоритм сортировки простым обменом основан па 'К Сортировка принпипе сравнения и обмена пары соседних элементов до тех »ор, пока не будут рассортированы все элементы. Как и в предыдущих методах простого выбора, мы совершаем повторные проходы по массиву, каждый раз просеивая наименьший элемент оставшегося множества, двигаясь к левому конку массива. Если, для разнообразия, мы будем рассматривать массив, расположенный вертикально, а не горизонтально и — при помощи некоторого воображения — представим себе элементы пузырьками в резервуаре с водой, обладающими «весами», соответствующими их ключам, то ка>кдый проход по массиву приводит к «всплыванню» пузырька на соответствующий его весу уровень (см, табл.
2.3). Этот ме- Таблица 2.3. Пример сортировки методом пузырька Ю з г ез И М <Ч Фа«а»злые и «змее е Н 1о з м з тод широко известен как сортировка методом пузырька. Его простейший варнант приведен в программе 2.4. ргосейнге ЬиЬЫезогг; чаг Ц! 1пбех; хп йет; Ьей(п $ог 1:= 2 то п оо Ьеа!п 1ог,7:= н йони!о т йо Иа!7' — 1] .7сеу > а17] Аеу тйеп Ьей(п х : = а]7'-1]; а]7' — 1]: = аН; аИ :=- зс пй епй епй (ЬиЬЫелогг] Программа 2.4. Сортировка методом пузырька.
, Этот алгоритм легко оптимизировать. Пример в табл. 2.3 показывает, что три последних прохода никак не влияют на порядок элементов, поскольку те уже рассортированы. Очевидный способ улучшить данный алгоритм в это запоминать, производился ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот пропете улучшения можно продолжить, если запоминать пе только сам факт обмена, но и место (индекс) последнего 44 55 12 42 94 !8 06 67 06 06 06 06 06 06 06 44 12 12 12 12 12 12 55 Г44 1в 16 18 ' 18 18 12 ~ 55 ~44 г 42 42 42 42 42 1~ 18-з 55 ~ 44 — е-44 44 44 94 ~ 42 42 55 55 †» 55 55 18 94 гь- 67 67 67 67 — ~ 67 67 67-г 94 94 94 94 94 22 лаоргнровкв мосс«вон 85 обмена.
Ведь ясно, что все пары соседних элементов с индексами, меньшими этого индекса й, уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе, вместо тога чтобы двигаться до установленной заранее нижней границы й Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный «пузырек» в «тяжелом» конце рассортированного массива всплывет на место за один проход, а неправильно расположенный элемент в «легком» конце будет опускаться на правильное место талька иа один шаг на каждом проходе. Например, массив 12 18 42 44 55 67 94 06 будет рассортирован прн помощи метода пузырька за один проход, а сортировка массива 94 06 !2 18 42 44 55 67 потребует семи проходов. Эта неестественная асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов.
Мы назовем полученный в результате алгоритм шейкер-сортировкой. Его работа показана в табл. 2.4.на тех же восьми кл~ояах, которые использовалнсь в табл. 2.8. Табвнца 2.4. Лрянер огеакер-сортировка 3 3 4 4 8 7 7 4 г 8 Анализ сортировки методом пузырька и шейкер-сортировки. Число сравнений в алгоритме простого обмена равно С= » (и' — и), (2. 1О) минимальное, среднее и максимальное количества пересызк (присваиваний элементов) равны Ыо»„=0, Ы, =-,(ие — и), М„,„=-,:(и — и).
(2.!1) 44 55 12 42 94 18 66 67 44 44 ! — »-12 12 55 12 — ! 44 18 94 18 55 55 18 67 67 67 67 ь е 94 94 94 88 2. Сортировка рсосеопсв а1«акегвог«; гас 1',1г,!,г: 1п«1ех; х; «Уев; Ьей1п 1:= 2; г:=- и; Й".=- л; серея« 1ос,1:.== г йоппсо 1 йо И а11 — Ц .кеу .
аК,йеу йеп Ьей1п х:= аУ вЂ” Ц; а«1 — Ц:= 4Я; а»Я: х; 1с:= 1 ерй; 1:= й+1; 1ог 1:= 1 1о г оо 11 аУ вЂ” Ц .йеу > аИ .йеу СЬеп Ьей1п х:= — а11 — 1»'„а~1«-Ц;= а11»1 аИ:= х; й:= 1' епй ; «:= 1с — 1; пп«11 1 > г епй 1вйайегаогС» Программа 2.8. Шебкер-сортировка. Анализ улучшенных методов, особенно метода шейкер-сортировки, довольно сложен. Наименьшее число сравнений есть С ы = и - — 1. Для усовершенствованного метода пузырька Кнут получил, что среднее число проходов пропорционально л — й, ~''и н среднее число сравнений пропорционально ,— '-~й — иА+!пи)1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
