Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 14
Текст из файла (страница 14)
В частности, сортировка является идеальным примером огромного разнообразия алгоритмов, вьшолняющих одну и ту же задачу, многие из которых в некотором смысле являются оптимальными, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. Кроме того, здесь мы увчдим, как при помощи усложнения алгоритмов можно добиться значительного увеличения эффективности по сравнению с более простымн и очевидными методами.
Зависимость выбора алгоритмов от структуры данных— явлсцнс довольно частое, н в случае сортировки она настолько 2.д Введение сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка (последовательных) файлов. Эти два класса часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ; для этой памяти характерен быстрый произвольный доступ, а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.
е. на запоминающих устройствах с механическим Рвс. 2й. Сортировка массива, передвижением (дисках и лентах). Это существенное различие можно наглядно показать на примере сортировки пронумерованных карточек. Представление карточек в виде массива соответствует тому, что все они располагаются перед сортирующим так, что каждая карточка видна и доступна (см. рис, 2.!).
Представление карточек в виде файла предполагает, что видна только верхняя карточка из каждой стопки (см. рис. 2.2). Очевидно, что такое ограничение приведет к существенному изменению методов сортировки, но оно неизбежно, если карточек так много, что их число нз столе не уменьшается. Прежде всего мы введем некоторую терминологию и систему обозначений, которые будем использовать в этой главе. Нам даны элементы сть ав~ ' 1 ав Сортировка означает перестановку этих элементов в таком порядке: что при заданной функиии упорядочения 1 справедливо отношение )(ав,') ~)(ав,)к ... ~Цав„). (2.1) 76 2. Сортировка Обычно функция упорядочения не вычисляется по какому-то специальному правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называется ключом элемента.
Следовательно, для представления элемента а; особенно хорошо подходит структура записи. Поэтому мы определяем тип тает (элемент), который будет Рвс. 2.2. Сортировка файла. использоваться в последующих алгоритмах сортировки следующим образом; то )гву; (оаисаи (2,2) «Прочие компоненты» — это все существенные данные об элементе; поле йеу — ключ служит лишь для идентификации элементов.
Однако, когда мы говорим об алгоритмах сортировки, ключ для нас — единственная существенная компонента, н нет необходимости как-то определять остальные. Выбор в качестве типа ключа целого тппа достаточно произволен; ясно, что точно так же можно использовать н любой тнп, на котором задано отношение всеобщего порядка. Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется прп сортировке, Устойчивость сортировки часто бывает желательна, если элементы упорядочены (рассортнрованы) по каким-то вторичным ключам, т. е.
по свопствам, не огратьснным в первичном ключе. 2.2. Сортировки масоивоо Пе следует считать, что данная глава представляет собой исчерпывающий обзор методов сортировки. Здесь лишь особенно подробно разбираются некоторые избранные методы. Заинтересованного читателя, желающего получить полное представление о сортировке, мы отсылаем к блестящей н всеобъемлющей работе Д. Кнута 12.71 (см. также (2.101).
2.2. СОРТИРОВКА МАССИВОВ Основное требование к методам сортировки массивов— экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять (п з1(и (на том же месте) и что методы, которые пересылают элементы из массива а в массив Ь, не представляют для нас интереса.
Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов мы проводим в соответствии с их эффективностью, т. е. экономией времени или быстродействием. Удобная мера э44ективности получается при подсчете числа С вЂ” необходимых сравнений «лючей и М вЂ” пересылок элементов.
Эти числа определяются некоторыми функциями от числа и сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка и 1оп и сравнений, мы сначала обсудим несколько несложных и очевидных способов сортировки, называемых простыми методами, которые требуют порядка и' сравнений ключей.
Мы решили рассмотреть простые методы прежде, чем перейти к более быстрым алгоритмам, по следующим трем важным причинам: 1. Простые методы особенно хорошо подходят для разъяснения свойств большинства принципов сортировки. 2. Программы, основанные на этих методах, летии для понимания и коротки. Следует помнить, что программы также занимают память! 3. Хотя сложные методы требуют меньшего числа операций, эти операции более сложны; поэтому при достаточно малых а простые методы работают быстрее, но их не следует использовать при больших п. Методы, сортирующие элементы 1п з(ти, можно разбить на три основных класса в зависимости от лежащего в их основе приема: 1.
Сортировка включениями. 2. Сортировка выбором. 3. Сортировка обменом. Теперь мы рассмотрим и сравним эти три принципа. Программы работают с переменной-массивом а, компоненты 2. Сортировка которой нужно рассортировать 1а 811и. В этих программах используются типы данных Иелт (2.2) и !паек, определенные так; (2.3) 1.1Л. Сортировка простыми включениями. Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются иа готовую последовательность аь ..., а~ ~ и входную последовательность аь ..., а„. На каждом шаге, начиная с 1= 2 и увеличивая ~' на единицу, берут рй элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.
Таблица 2.1. Пример сортировки простыми включеииими 18 06 67 18 06 67 18 06 67 13 06 67 67 67 44 55 12. 42 44 55 1 42 2 44 55 12 2 44 55 Процесс сортировки включениями показан на примере восьми случайно взятых чисел (см. табл. 2.!). Алгоритм сортировки простыми включениями выглядит следу5ощим образом: 1ог1:= 2, 1о а до Ъео1п к:= а И~ «вставить х на подходящее место в а, ... а,» епц Прн поиске подходящего места удобно чередовать сравнения и пересылки, т. е. как бы «просеивать» х, сравнивая его с очередным элементом а~ и либо вставляя к, либо пересылая а1 направо и продвигаясь налево, Заметим, что «просеивание» может закончиться при двух различных условиях: 1.
Найден элемент а~ с ключом меньшим, чем ключ х. 2. Достигнут левый конец готовой последовательности. Этот типичный пример цикла с двумя условиями окончания дает нам возможность рассмотреть хорошо известный прием На«а«»нате «лючц Г 2 1 3 1 4 1 5 1 б 7 7 1 8 06 12 18 42 44 55 67 9~~-7~ З.З. Сортировка моссиаоа фиктивного элемента («барьерав). Его можно легко применить в этом случае, установив барьер ас = х. (Заметим, что для этого нужно расширить диапазон индексов в описании а до О...,, и,) Окончательный алгоритм представлен в виде лрограммы 2.1. ркоееймке лкга1Я!тзегт(ол) так 1,): уяс)ех; х: йет; Ъей1а аок 1: = 2 ко и йо Ъерп х:= а(1); а10):= х;,1:= 1 — 1; еЪПех кеу .
аК.йсуйо Ъерп а()+1):= аИ:,) .'=,)' — 1; епй; а[у+Ц:= х епй еай Программа 2Л. Сортировка простыми включениями. Анализ сортировки простыми включениями. Число С~ сравнений ключей прн Ом просеивании составляет самое большее 1 — 1, самое меньшее 1 н, если предположить, что все перестановки а ключей равновероятны, в среднем равно 1/2. Число М; пересылок (присванваний) равно С;+2 (учнтывая барьер). Поэтому обшее число сравнений и пересылок есгь С ~„— — п — 1 М м —— 2(л — 1) С,р — — —,(пт+ и — 2) М,р — — -', (и'+ Ои — 1О) (2.4) Стаса = я (пт + и) — 1 Мюаа = я (ли + Зп — 4) Наименьшие числа появляются, если элементы с самого начала упорядочены, а наихудший случай встречается, если элементы расположены в обратном порядке.
В этом смысле сортировка включениями демонстрирует вполне естественное поведение. Ясно также, что данный алгоритм описывает устойчивую сортировку: он оставляет неизменным порядок элементов с одинаковыми ключами. Алгоритм сортировки простыми включениями легко можно улучшить, пользуясь тем, что готовая последовательность аь ..., а; и в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее. Очевидно, что здесь можно применить бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения, Модифицированный алгоритм сор. 2. Сортировка тировки называется сортировкой бинарными включениями, он показан в программе 2.2, рсосейше Бглагу!лхе«11ол; тас Ц,1,«,т: йЫех; х: 11гт; Ьерп уос 1: =- 2 !о и йо Ьерп х:= а[1]; 1:=* 1; г:= и' — ! нйй!е1 ~ гав Ъей!и т: = (1+«) й!и 2; Их.1«еу ( а[гл] .1сгу !Ъеп г:= т-1 е)не 1;=- гл+1 евй; Го«1 '.= 1-1 йоив!о1йо а[1+1]:= а[Я; а[1]:=- х епй епй Программа 2.2, Сортировка бинарными включениями.
Анализ сортировки бинарными включения» и. Место вклю- чения найдено, если аьйеу х.кер< а,.йгу. Таким образом, интервал поиска в конце должен быть равен 1; это означает, что интервал из 1 ключей делится пополам [!оия 1] раз. Итак, и С= Е [!ойа1], Мы аппраксимируем эту сумму с помощью интеграла н ~ !оя х йх = х (1ои х — с)~, = н (!Оя н — с) + с, (2б) 1 где с = !од е = 11'!и 2 = 1.442бй.... Количество сравнений не зависит от исходного порядка элементов.
Но из-за округле- ния при делении интервала поиска пополам действительное число сравнений для 1 элементов может быть на ! больше ожидаемого. Природа этого «перекоса» такова, что в ре- зультате места включения в нижней части находятся в сред- нем несколько быстрее, чем в верхней части. Это дает пре- имущество в тех случаях, когда элементы изначально далеки от правильного порядка. На самом же деле минимальное число сравнений требуется, если элементы вначале располо- жены в обратном порядке, а максимальное — если они уже упорядочены. Следовательно„это случай неестественного ло- ведения алгоритма сортировки: С =' и (1ои и — !од е ~ 0.5). К сожалению, улучшение, которое мы получаем, используя метод бинарного поиска, касается только числа сравнений, 22.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
