Лекция: Элементарные методы сортировки
Элементарные Методы Сортировки
В качестве нашей первой экскурсии в область алгоритмов сортировки, мы изучим некоторые "элементарные" методы которые хорошо работают для небольших файлов или файлов специальной структуры. Существует несколько причин, по которым желательно изучение этих простых методов. Во-первых, они дают нам относительно безболезненный способ изучить терминологию и основные механизмы работы алгоритмов сортировки, что позволяет получить необходимую базу для изучения более сложных алгоритмов. Во-вторых, для многих задач сортировки бывает лучше использовать простые методы, чем более сложные алгоритмы. И, наконец, некоторые из простых методов можно расширить до более хороших методов или использовать их для улучшения более сложных. В некоторых программах сортировки лучше использовать простые алгоритмы. Программы сортировки часто используются только один раз (или несколько раз). Если количество элементов, которые нужно отсортировать не велико (скажем меньше чем 500 элементов), то может статься, что использование простого алгоритма будет более эффективно, чем разработка и отладка сложного алгоритма. Элементарные методы всегда пригодны для маленьких файлов (скажем меньших, чем 50 элементов); маловероятно, что сложный алгоритм было бы разумно использовать для таких файлов, если конечно не нужно сортировать большое количество таких файлов. Как правило, элементарные методы, которые мы будем обсуждать, производят около операций для сортировки N произвольно взятых элементов. Если N достаточно мало, то это может и не быть проблемой, и если элементы распределены не произвольным образом, то эти алгоритмы могут работать даже быстрее, чем сложные. Однако следует запомнить то, что эти алгоритмы не следует использовать для больших, произвольно упорядоченных файлов, с одним единственным исключением для алгоритма оболочечной сортировки, который часто используется во многих программах.Правила Игры
Перед тем, как рассматривать какой-либо конкретный алгоритм, было бы полезно изучить терминологию и некоторые основные соглашения об алгоритмах сортировки. Мы будем изучать алгоритмы для сортировки файлов записей содержащих ключи. Ключи, которые являются только частью записи (часто очень маленькой их частью), используются для управления процессом сортировки. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в некотором строго определенном порядке (обычно в алфавитном или числовом). Если сортируемый файл целиком помещается в память (или целиком помещается в массив), то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой. Главное отличие между ними состоит в том, что при внутренней сортировке любая запись легко доступна, в то время как при внешней сортировке мы можем пользоваться записями только последовательно, или большими блоками. Большинство алгоритмов сортировки, которые мы рассмотрим Ц внутренние. Обычно, главное, что будет нас интересовать в алгоритме Ц это время его работы. Первые четыре алгоритма, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное , в то время как более сложные алгоритмы используют время пропорциональное . (Можно показать, что никакой алгоритм сортировки не может использовать менее, чем сравнений между ключами.) После изучения простых методов мы рассмотрим более сложные методы, время работы которых пропорционально и методы использующие бинарные свойства ключей для уменьшения общего времени работы до N. Количество используемой дополнительной памяти алгоритма сортировки Ц это еще один важный фактор, который мы будем принимать во внимание. Вообще говоря, методы сортировки делятся на три типа: методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива; методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти; и методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла. Стабильность Ц еще одна немаловажная характеристика методов сортировки. Метод сортировки называется стабильным, если он сохраняет относительных порядок следования записей с одинаковыми ключами. Например, если алфавитный список группы сортируется по оценкам, то стабильный метод создает список, в котором фамилии студентов с одинаковыми оценками будут упорядочены по алфавиту, а нестабильный метод создаст список в котором, возможно, исходный порядок будет нарушен. Большинство простых методов стабильны, в то время как большинство хорошо известных сложных методов Ц нет. Если стабильность необходима, то она может быть достигнута посредством добавления к ключу небольшого индекса перед сортировкой или посредством удлинения, каким-либо образом, ключа. Стабильность с легкостью принимается за норму; к нестабильности люди относятся с недоверием. На самом же деле, лишь немногие методы достигают стабильности без использования дополнительного времени или места. Следующая программа, для сортировки трех записей, предназначена для иллюстрации основных соглашений, которые мы будем использовать. В частности, главная программа любопытна тем, что она работает только для N=3; смысл в том, что любая программа сортировки может быть сведена к процедуре sort3 этой программы. Три оператора присвоения, каждый из которых сопровождается оператором if, на деле реализуют операцию УобменаФ. Мы вставляем ее непосредственно в программный код вместо использования вызова процедуры, поскольку они являются основой многих алгоритмов и часто попадают внутрь цикла. Чтобы сконцентрироваться на алгоритмических вопросах, мы будем работать с алгоритмами, которые просто сортируют массивы целых в численном порядке. В общем, очень легко адаптировать такие алгоритмы для практического использования, включающего в себя работу с большими ключами или записями. В основном программы сортировки работают с записями двумя способами: либо они сравнивают и сортируют только ключи, либо передвигают записи целиком. Большинство алгоритмов, которые мы изучим можно применять, посредством их переформулировки в терминах этих двух операций, для произвольных записей. Если сортируемые записи довольно большие, то обычно пытаются избежать передвижения их посредством лкосвенной сортировки: при этом сами записи не переупорядочиваются, а вместо этого переупорядочивается массив указателей (индексов), так, что первый указатель указывает на самый маленький элемент и так далее. Ключи могут храниться либо с записями (если они большие), либо с указателями (если они маленькие). Если необходимо, то после сортировки записи можно упорядочить. Это описано дальше.
program treesort; const maxN=100; var a : array [1..maxN] of integer; N, i : integer; procedure Sort3; var t : integer; begin if ( a[1] > a[2] ) then begin t := a[1]; a[1] := a[2]; a[2] := t; end; if ( a[1] > a[3] ) then begin t := a[1]; a[1] := a[3]; a[3] := t; end; if ( a[2] > a[3] ) then begin t := a[2]; a[2] := a[3]; a[3] := t; end; end; begin readln( N ); for i:=1 to N do read(a[i]); if N=3 then sort3; for i:=1 to N do write(a[i]); writeln; end; |
Сортировка Выбором
Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов, как показано на рисунке 1. При первом проходе символ пробела уходит на первое место, обмениваясь с буквой СПТ. На втором проходе элемент СВТ обменивается с элементом СРТ и так далее. Следующая программа дает полную реализацию этого процесса. Для каждого i от 1 до N-1, она обменивает наименьший элемент из a[i..N] с a[ i]:рисунок 1 Сортировка выбором |
procedure selection; var i,j,min, t : integer; begin for i:=1 to N-1 do begin min := i; for j:=i+1 to N do if a[j]<a[min] then min := j; t := a[min]; a[min] :=a[i]; a[i] := t; end; end; |
Сортировка Вставкой
Метод сортировки вставкой, почти столь же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отортированными).рисунок 2 Сортировка вставкой |
procedure insertion; var i, j, v : integer; begin for i := 2 to length(str) do begin v := a[i]; j:=i; while (a[j-1]>v) do begin a[j] := a[j-1]; dec(j); end; a[j] := v; end; end; |
Пузырьковая Сортировка
Элементарный метод сортировки, который часто дают на вводных занятиях Ц это пузырьковая сортировка: Стоящие рядом элементы массива обмениваются местами, до тех пор, пока встречаются неотсортированные пары. Реализация этого метода дана ниже.procedure bubble; var i,j, t : byte; begin for i := 100 downto 1 do for j:=2 to i do if x[j-1]>x[j] then begin t:=x[j-1];x[j-1]:=x[j];x[j]:=t; end; end; |
Характеристики Простейших Сортировок
Свойство 1 Сортировка выбором использует около сравнений и N обменов. Свойство 2 Сортировка вставкой использует около сравнений и обменов в среднем, и в два раза больше в наихудшем случае. Свойство 3 Пузырьковая сортировка использует около сравнений и обменов в среднем и наихудшем случаях. Свойство 4 Сортировка вставкой линейна для лпочти сортированных файлов. Свойство 5 Сортировка выбором линейна для файлов с большими записями и маленькими ключами.Сортировка Файлов с Большими Записями
Очень часто бывает возможно (и желательно) сделать так, чтобы при сортировке файла состоящего из N элементов любом методом было бы сделано только N операций обмена полной записи посредством косвенной адресации к элементам массива (используя массив индексов или указателей), а саму реорганизацию делать после. Более конкретно: если массив a[1..N] содержит большие записи, то мы предпочтем использовать массив указателей p[1..N] для того, чтобы знать, где находится очередной элемент массива a, и для произведения псевдообмена. Ниже приведена программа сортировки вставкой с использованием массива указателей:procedure insertion; var i, j, v : integer; p : array[1..N] of integer; begin for i:=1 to N do p[i] := i; for i := 2 to length(a) dobegin v := p[i]; j:=i; while a[p[j-1]] > a[v] dobegin p[j] := p[j-1]; j:=j-1; end; p[j] := v; end; end; procedure rearrange; var i,j,k,t : integer; begin for i:=1 to length(a) do if p[i]<>i thenbegin t:=a[i]; k:=i; repeat j := k; a[j]:=a[p[j]]; k:=p[j]; p[j]:=j; until k=i; a[j]:=t; end; end; |
рисунок 6 Переупорядочение лсортированного массива |
Сортировка Шелла
Сортировка вставкой работает медленно потому, что она обменивает только смежные элементы. Оболочечная сортировка является простейшим расширением сортировки вставкой, которая увеличивает скорость работы алгоритма за счет того, что позволяет обменивать элементы находящиеся далеко друг от друга. Основная идея алгоритма состоит в том, чтобы отсортировать все группы файла состоящие из элементов файла отстоящих друг от друга на расстояние h. Такие файлы называются h-сортированными. Когда мы h-сортируем файл по некоторому большому h, мы передвигаем его элементы на большие растояния. Это облегчает работу сортировки для меньших значений h. Процесс заканчивается когда h уменьшается до 1.рисунок 7 Оболочечная Сортировка |