Лекции по информатике (984119), страница 18
Текст из файла (страница 18)
7 Кь-г: 1' Двоггчггкгг1 поиск, це сравнений сггиогсаетсл с и до 1оиа и 3 иЬ11е Ь < К с1о Ьеи1п 1' При Л > Л агесто вставки обнаружено 3 гп:=- [Ь + К) с11т 2: 11 а(ш) < х ФЬеп лп -'- 1 е1ве К : — лп; епс1; Сдавав оспшюсасл, с»,ож:люслпь О!и ) Ког ): ! с1отл~псо К вЂ”; 1 с1о а() ): а() — Ц; а(Щ: х; епс1; епс1; Анализ алгоритма двоичной вставки.
Место включения обнаружено, если Л = Л. Таким образом, в конце поиска интервал должен иметь единичную длину: деление погюлам проводится 1 1оя, ! раз, и число сравнений будет С = ~~~ ~!о6 л1, где верхние полускобки (х1 означают минимальное целое, большее х [76].
При увеличении числа слагаемых и сумму можно аппроксимировать интегралом: 1 где с = !ои с = = 1,4426, т. е. среднее число сравнений не зависит от начального !п2 порядка элементов. Если в исходном состоянии элементы упорядочены, то, из-за отбрасывания дросбллой части при половинном делении, двоичный попс:к дает чуть большее число сравнений, а если упорядочены в обратнуло сторону., то чуть меньше. При отсортированном массиье мы ьыполняем только 2!и — 1) встречное копирование в переменную х и обратно.
Сдвиг не нужен и сортировка раоотает за линейное время. К сожалению, частичное ускореллие с 0(п) до 0(1одп), даваемое двоичньп| поиском, касается лишь части трудоелллслюти сортировки вставкой сравнений. Главный чтлен сложностной оценки ЛХ продолжает осталлаться квадратичным. Сортировка, двоичной вставкой может быть полезна только в том случае, когда сравнение занимает гораздо болыпе времени, чем копирование элементов. Например, если необходимо отсортировать множество строк, заданное массивом указателей типа сЬагл* (в языке Си), то сравнение элементов (просмотр двух строк до первого несовпадения) выполняется гораздо дольше, .чем их копирование, т.
к. время сравнения двух строк есть 0(п), а время перестановки строк, выполняемое копированием указателей, 0(1). Таким образом, низкая производительность метода вставки -- следствие группового сдвига всех отсортированных элементов при вставке каждого нового -- сохраняется и при двоичной вставке. Этот метод, так же, как и простая вставка, не рекомендуется к практическому применению на сколько-нибудь больших массивах. 6.2.2.2 Сортировка выборкой Алгоритм основан на простой идее: ° процесс повторяется для оставшихся п, — 1-ого, п, — 2-х, ... элементов до тех пор, пока не останется один, самый большой элемент. Метод выборки в некоторым смысле противоположен методу вставки.
При прямой вставке на каждом шаге рассматривается только один очередной элемент исходной последовательности и все элементы готовой последовательности, среди которых отьнткивается место вставки. При прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы исходной последовательности, и найденный минимальный элемент помещается в выходную последовательность как очередной элемент. Поскольку сортировка выборкой также выполняется на месте и обмен возможен ввиду прямого доступа к элементам массива, то вместо удаления минималыюго элемента из входной последовательности на, его место помещается очередной рассматриваемый элемент аг, который будет впоследствие обязательно рассмотрен среди оставшихся элементов.
Ниже приведен пример работы сортировки выборкой для последовательности 44 55 12 42 94 18 06 67 (ттереставленттьте элементы выделены полужирным шрифтом, курсивом набраны минималып.те элементы в неотсортированных ттотцтоследовательттостях): Исходные ключи г=1 г= 2 г= 3 г= 4 г=5 г=б г= 7 Заметим, что на 4-ом и 6-ом шагах элемецты уже оказались на своих местах, но они все-таки были два>тсдьт обменены сами с собой. ргосес1тне 81гЯе18отт(ттаг а: вес1): 1' Со1тттгировка тгрямым выбороги — стандартный алгорипгм тт те Осглосттгои' прггнцип: берем элемент с ттатлменьилим, ключом и ставим его на ггервое место, меняя с а11]. Затем проиелс повторяем для элеметгтпов а1г1..а1тг — 11' (т. к. а11/ — уоюе аиигимальнътй иэ рассмсттттрстнтгих) т айаг т, 1, 1: тттс1ех; х: тсстп: 1' Здесь х — длЯ пеРестановки, а не длЯ сдвига, тт Ьентп Гог т: 1 Со и — 1 с1о Ьентп х: а~т ~: 1' Берем очередной элелгснтп...
тт е отыскивается элемент с наименьшим ключом; ° он меняется местами с первыкл элементом ат., Схема алгоритма сортировки выборкой такова Гог т: - 1 $о и — 1 с1о Ьентп 1' присвоить 1г индекс наименьшего иэ а1г.. п~ т 1' тгоменять лгестамтг а~Ц и тт1г1 3 епс1; 44 55 12 42 94 06 55 12 42 94 06 12 55 42 94 06 12 18 42 94 06 12 18 42 94 06 12 18 42 44 06 12 18 42 44 06 12 18 42 44 18 06 67 18 44 67 18 44 67 55 44 67 55 Д 67 бб 94 67 55 94 67 55 67 94 1с: г: г' ...
и запоминаслг его индекс л !' Ищем минимальный среди остильньгсс лг Гог г:-! ль1$оггс1о !' Бстретпилсл лгсныиий въгбранного — запоминаем его значенгле и глндекс и гг!годолгэгсаем поиск 3 Ы а1! ~ < х ФЬеп Ье! 1п х: а~1'1; епс1; !' Перестановка гпскущего элемента с на меньшим в подпоследоватсльности а1Ц: . а!1 ): а!1): — х; епс1; епс1; Доказательство корректггогти этого алгоритма несложно и осуществляется по индукции. Шаг индукпии основан на том, что по определению минимального элемента множества минимальный среди оставшихся не мепсипе максимального среди ранее извлеченных минимальных элементов. Проанализируем алгоритм выборки.
Число сравнений ключей п — и 2 2 не зависит от их начального порядка. То есть этот метод не обладает естественной отзывчивостью на предварительную упорядоченность элементов в части их сравнения. Число перестановок минимально в случае уже упорядоченных ключей и равно 3(гг, — 1). Если изначально ключи были распологкены в обратном порядке, то число перестановок максимально: и' ЛХ„,, = — ! 3(и — 1) 4 Для того, чтобы определить л14 „и необходимо рассужда,ть так: алгоритм просматривает массив, сравнивая каждый элемент с только что обнаруженной минимальной величиной; если он меньше первого, то выполняется некоторое присваивание. Вероятность того, что третий элемент окажется меньше двух первых, равна 1Л3, вероятность оказаться минимальным для четвертого - 1Л4 гл т.
д. Поэтому общее число ожидаемых пересылок 1 1 1 равно — + — 1 ... -! — = ̈́— 1, где Н„п-ое гармоническое число, Это число можно п, выразить еще таким способом: 1 1 Н„= 1пп+ д+ — —, + .. 2п 12иг где д = 0,577216...
константа Эйлера. Для достаточно больгпих и можно игнорировать дробные составляющие, поэтому среднее чис:го присваиваний на г-том просмотре аппроксимирустся выражением К =!пг'+ д+ 1. Среднее число пересы.юк ЛХ „д в сортировке выборкой есть сумма Х'1: в Л'Х,,д — — п(ее+ 1) + е !пав. а=1 Вновь аппроксимируя эту сумму дискретных членов интегра,юм 11 е с 1п х ох = х(1п х — 1) = и 1п и — и + 1 1 получаем, наконец, приблизительное значение ЛХ,,„, = п(1пп 1 д). Отсюда можно сделать заключение, что, как правило, алгоритм сортировки выборкой предпочтительнее простой встаьки.
Однако, если к:почи вначале упорядочены или почти упорядочены, алгоритм вставки будет оставаться несколько более быстрым. 6.2.2.3 Обменные сортировки Смешать. Но не взбалтывать Джеймс Бонд В данном разделе мы опишем простой метод сортировки, в котором обмен местами двух элементов производится не с целью вставки или выборки, а неееосредственно для упорядочения. 1'ак называемый алгоритм прямого обмена, основывается на сравнении и перестановке пар соседних элементов до тех пор, пока, таким образом не будут упорядочены все элементы.
Как и при сортировке выборкой мы осуецсствляем проходы по массиву, постепенно сдееиГяя наимшеыпий элемент Ос'Гявшейся ееосееедовеетееее ности к .левОму краео массива. Если мы откажемся от горизонтальной ориентации сортирусмых последовательностей в пользу вертикальной, то упорядочение этим методом можно интерпретировать как всплытие (погружение) пузырьков в чане с водой (в стеклянной колонно с пивом) сообразно их весу, точнее, плотности. Этот гидрогазодинамический смысл обменной сортировки и дал ей более популярное название герзьчръкоооей сортировки.
Сразу внесем в нашу переборную идею такое улучшение: поскольку легчайший пузырек всплывает наверх всего за, один проход, то при последущих просмотрах можно исклю дать из рассмотрения по одному такому элементу и тем самым несколько ускорить пузырьковую сортировку. Вспомните сортировку выборкой, когда минимум отыскивался не во всей последовательности, а в ее нерассмотренном остатке! Пузырьковая сортировка столбца с ранее рассматриваемыми данными: 44 , Об 611 Об О6 Об Об Об 55 ; 44 , ° 12 12 12 12 12 12 12 : 55 .' 44 , ° 18 18 18 18 18 42 : 12 ° 55 .' 44 ..42 42 42 42 94 : 42 18 ' 55 ' 44 ° ° ° ° 44 44 44 18 : 94 42 42.' 55 55 .
55 55г 06 18 94 67 67 67 67. " 67 67 67 67 94 94 94 94 94 ргосес1пге ВпЫг1е8ог11уаг а: вес1); ( Сортировка прямым обменом — пузырьковая, обллен здесь характернейилая особенность процесса, сортировки г ( Основной пригн;агн на ка:ж.дом проходе сравпиванпася два соседних элсмегигга и обмсниваготся местами, Продолэгсаггпгея до тех пор, пока зла»ленты, нс будут уггорядонены,. Ледостатки: (1,1 на ггогледгигх проходах элементьг могут уэгсе бытг> уггорядо>лгггсьс. (91 Пузырек всгьлывает быстро (за, 1 проход до сгерхгд), а танели,ллсдленно (за 1 проход на 1 ггозиглиго) «Применяетсяг НИКОГДЛ1» Д. В. Соигникоо гг лиг 1, 1, 1с: 1пс1ех; х: 1сеш; Ьеиш 4Ьг1: 2~оп 1о Гог г: и с1ои>пСо 1 с1о Ьеиш М а[г — 1[ > а[1[ ФЬеп Ьеи1п (и, ~ — > а,,1 х: а[1 — 1[; а[1 — 1[ э — гг[1 [: а[1[: -- х; епс1; епс1; епс1; Из нашего примера видно, что три последних прохода не влияют на порядок элементов из-за того, что все они ужо отсортированы.
Эти лишние проходы запланированы на случай самой плохой входной последовательности, в которой на первом месте расположен ес ма,ксимальный элемент. Однако., если на каждом проходе вести подсчет числа состоявшихся обменов [или фиксировать сам факт обменов), то можно улучшить пузырьковую сортировку: ргосес1пге Вгг1г51еЕгг1г8огс[з>аг а: во<11; ( Сортировка прямььм обменом — ггггзырьковая улунгаенвая 1' ( Основной принцип: сали ълеллсглгпьл уэлсе упорядочены, сортировка прекраилаепгся айаг 1, 1', 1с: шс1ех; х: 11сгп:, ( згаар1гсд, г Ьоо1еггп; — факлгг обллена гг Ьеиш 2; гереа$1' Невовмоаюность досрочного окончания цикла, с на1>аметром в стандарте. Ппс>саля. приводит н ииклр с >гострсловием 1 1' ~от 1:= й го и а>о 1>едхп у' 1г г- 0; 1' Количество об>ванов данного прохода х~ 1' ви>аррес1;=- 7а1»е; — обменов не было >~ 1' 1 врвьрьков роке всг>лье«о, их просматрив>ать не нржно >> 1ог >; п с1о»упСо 1 с1о Ьеи1п Ы а Ц вЂ” 1]:» а]>] ФЬеп Ьеи1п 1' а, »-> а, у и: хЦ вЂ” 1]; а]1 — 1]:-- а]] ]: аЦ] ь- и; 1г ь-- 1с+ 1; 1 ви>арреа > = ггие; у' епс1; епс1; ппЫ к =- 0 ог» и 1 ог по1 в>оарред ~; епс1; Еще одно улучшение пе только фиксировать наличие обмена,, но и запоминать индекс последнего состоявшегося обмена, Е Поскольку все пары соседних элементов выше индекса й уже упорядочены, просмотры можно заканчивать на этом индексе, большем нижнего предела параметра цикла 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
