2. Алгоритмы внутренней сортировки. Элементарные методы сортировки
В качестве нашей первой экскурсии в область алгоритмов сортировки, мы изучим некоторые "элеметарные" методы которые хорошо работают для небольших файлов или файлов специальной структуры. Существует несколько причин по которым желательно изучение этих простых методов.
Во - первых, они дают нам относительно
безболезненный способ изучить
терминологию и основные механизмы работы
алгоритмов сортировки что позволяет
получить необходимую базу для изучения
более сложных алгоритмов.
Во - вторых, для многих задач сортировки
бывает лучше использовать простые методы,
чем более сложные алгоритмы. И наконец
некоторые из простых методов можно
расширить до более лучших методов или
использовать их для улучшения более
сложных.
Как было замечено ранее, в некоторых
программах сортировки лучше использовать
простые алгоритмы. Программы сортировки
часто используются только один раз (или
несколько раз). Если количество элементов
которые нужно отсортировать не велико (скажем
меньше чем 500 элементов), то возможно, что
использование простого алгоритма будет
более эффективно, чем разработка и отладка
сложного алгоритма. Элементарные методы
всегда пригодны для маленьких файлов (скажем
меньших чем 50 элементов); маловероятно, что
сложный алгоритм было бы разумно
использовать для таких файлов, если конечно
не нужно сортировать большое количество
таких файлов.
Как правило, элементарные методы, которые мы будем обсуждать, производят около N2 операций для сортировки N произвольно взятых элементов. Если N достаточно мало, то это может и не быть проблемой, и если элементы распределены не произвольным образом, то эти алгоритмы могут работать даже быстрее, чем сложные. Однако следует запомнить то, что эти алгоритмы не следует использовать для больших, произвольно упорядоченных файлов.
Перед тем, как рассматривать какой-либо конкретный алгоритм, было бы полезно изучить терминологию и некоторые основные соглашения об алгоритмах сортировки.
Под сортировкой понимают, процесс перестановки объектов множества в определенном порядке.
Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в каком-либо строго определенном порядке (обычно в алфавитном или числовом).
Пусть на дана последовательность
элементов: a1, a2, ..., an сортировка означает -
перестановку этих элементов в таком
порядке: ak1,ak2, .. ,akn, что при
заданной функции упорядочивания f(x),
справедливо отношение :
f(ak1) <= f(ak2)<= ..
<= f(akn) -
функция упорядочивания не вычисляется, а
содержится в каждом элементе в
виде явной компоненты и ее значение
называют ключом элемента. Следовательно,
для представления i-ого элемента
последовательности наилучшим образом
подходит структура записи. Определим тип
элемента, который будем использовать в
алгоритмах сортировки следующим образом :
type elem = Record
key: integer;
описание др. компонентов
end;
Поле key - служит только для идентификации
элемента.
Как здесь видно ключи являются только частью записи (часто очень маленькой их частью), используются для управления процессом сортировки.
Если сортируемый файл целиком помещается в память (или целиком помещается в массив, то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой.
Главное отличие между ними состоит в том,
что при внутренней сортировке любая запись
- легко доступна, в то время как при внешней
сортировке мы можем пользоваться записями
только последовательно, или большими
блоками.
Обычно, главное, что будет нас интересовать в алгоритме - это время его работы. Время работы алгоритма характеризуется числом необходимых сравнений обозначаемых через С и число м необходимых пересылок элемента - M.
Простые алгоритмы, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное N2, в то время как более сложные алгоритмы используют время пропорциональное NlogN. (Можно доказать, что никакой алгоритм сортировки не может использовать менее, чем N logN сравнений между ключами.)
Количество используемой дополнительной памяти алгоритма сортировки - это еще один важный фактор, который мы будем принимать во внимание. Вообще говоря, методы сортировки делятся на три типа(по времени):
- методы сортировки которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;
- методы которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;
- методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.
Стабильность - еще одна немаловажная характеристика методов сортировки. Метод сортировки называется стабильным если он сохраняет относительных порядок следования записей с одинаковыми ключами.
Например, если алфавитный список группы сортируется по оценкам, то стабильный метод создает список в котором фамилии студентов с одинаковыми оценками будут упорядочены по алфавиту, а нестабильный метод создаст список в котором, возможно, исходный порядок будет нарушен.
Большинство простых методов стабильны, в то время как большинство хорошо известных сложных методов - нет. Если стабильность необходима, то она может быть достигнута посредством добавления к ключу небольшого индекса перед сортировкой или посредством удлинения, каким-либо образом, ключа.
Стабильность с легкостью принимается за норму; к нестабильности люди относятся с недоверием. На самом же деле, лишь немногие методы достигают стабильности без использования дополнительного времени или места.
Следующая программа, для сортировки трех записей, предназначена для иллюстрации основных соглашений, которые мы будем использовать. В частности, главная программа любопытна в том, что она работает только для N=3; смысл в том, что любая программа сортировки может быть сведена к процедуре sort3 этой программы.
Три оператора присвоения, каждый из которых сопровождается оператором if на деле реализуют операцию "обмена". Мы вставляем ее непосредственно в программный код вместо использования вызова процедуры, поскольку они являются основой многих алгоритмов и часто попадают внутрь цикла.
Чтобы сконцентрироваться на
алгоритмических вопросах, мы будем
работать с алгоритмами которые просто
сортируют массивы целых в численном
порядке. В общем, очень легко адаптировать
такие алгоритмы для практического
использования включающего в себя работу с
большими ключами или записями.
В основном программы сортировки работают
с записями двумя способами: либо они
сравнивают и сортируют только ключи, либо
передвигают записи целиком.
Большинство алгоритмов которые мы изучим
можно применять, посредством их
переформулировки в терминах этих двух
операций, для произвольных записей.
Если сортируемые записи довольно большие, то обычно пытаются избежать их передвижения посредством "косвенной сортировки": при этом сами записи не переупорядочиваются, а вместо этого переупорядочивается массив указателей (индексов), так, что первый указатель указывает на самый маленький элемент и так далее. Ключи могут храниться либо с записями (если они большие), либо с указателями (если они маленькие). Если необходимо, то после сортировки записи можно упорядочить, как это описано дальше.
Программа демонстрирует основные принципы работы с массивом и сортирует 3 элемента.
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;
Программа sort3 использует даже более
ограниченный доступ к файлу: это три
операции вида "сравнить две записи и
обменять их если нужно, чтобы поместить
запись с меньшим ключом на первое место".
Программы ограниченные к таким операциям
интересны, поскольку они подходят для
реализации на аппаратном уровне. Мы изучим
из более подробно позднее.
Используя программы которые работают на
глобальном массиве, мы тем самым игнорируем
"пакетные проблемы" которые могут
доставить немало хлопот в некоторых языках
программирования. Стоит ли передавать
массив процедуре сортировки как параметр?
Можно ли использовать одну и ту же
процедуру сортировки для сортировки
массива целых и массива вещественных (и для
массива произвольно сложных записей)? Даже
с нашими простыми допущениями, мы должны
обходить отсутствие в Паскале динамических
массивов посредством задания массива
максимального размера.
Сортировка Выбором
Один из самых простых методов сортировки
работает следующим образом: находим
наименьший элемент в массиве и обмениваем
его с элементом находящимся на первом месте,
потом повторяем процесс со второй позиции в
файле и найденный элемент обмениваем со
вторым элементом и так далее пока весь
массив не будет отсортирован. Этот метод
называется сортировка выбором поскольку он
работает циклически выбирая наименьший из
оставшихся элементов.
Сортировка выбором
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;
По мере продвижения указателя i слева
направо через файл, элементы слева от
указателя находятся уже в своей конечной
позиции (и их не больше уже не будут трогать),
поэтому массив становится полностью
отсортированным к тому моменту, когда
указатель достигает правого края.
Этот метод - один из простейших, и от
работает очень хорошо для небольших файлов.
Его "внутренний цикл" состоит из
сравнения a[i]<a[min] (плюс код необходимый для
увеличения j и проверки на то, что он не
превысил N), что вряд ли можно еще упростить.
Ниже мы обсудим то, сколько скорее всего раз
эти инструкции будут выполняться.
Более того, несмотря на то, что этот метод
очевидно является методом "грубой силы",
он имеет очень важное применение: поскольку
каждый элемент передвигается не более чем
раз, то он очень хорош для больших записей с
маленькими ключами. Это обсуждается ниже.
Сортировка Вставкой
Сортировка вставкой - это метод который
почти настолько же прост, что и сортировка
выбором, но гораздо более гибкий. Этот метод
часто используют при сортировке карт: берем
один элемент и вставляем его в нужное место
среди тех, что мы уже обработали (тем самым
оставляя их отсортированными).
type
Index = 0..n;
var
a: array[1..n] of elem;
procedure Insert;
var i,j: index;
x: elem;
begin
for i:= 1 to n do
begin
x:= a[i]; a[0]:= x;
j:= i-1;
while x.key <
a[j].key do
begin
a[j+1]:= a[j]; j:=
j-1;
end;
a[j+1]:= x;
end;
end;
Также как и в сортировке выбором, в
процессе сортировки элементы слева от
указателя i находятся уже в сортированном
порядке, но они не обязательно находятся в
своей последней позиции, поскольку их еще
могут передвинуть направо чтобы вставить
более маленькие элементы встреченные позже..
Однако массив становится полностью
сортированным когда указатель достигает
правого края.
Пузырьковая Сортировка
Следующий метод - это пузырьковая
сортировка. Проходить через массив,
обменивая если нужно элементы; когда на
каком-то шаге обменов не потребуется -
сортировка окончена. Реализация этого
метода дана ниже.
procedure bubble;
var i, j, t : byte;
begin
for i :=2 to N do
for j:=N down to
i do
if x[i-1]>x[j]
then
begin t:=x[j-1];x[j-1]:=x[j];x[j]:=t; end;
end;
end;
Чтобы поверить в то, что она на самом деле
работает, может потребоваться некоторое
время. Для этого заметьте, что когда во
время первого прохода встречаем
максимальный элемент, обмениваем его с
каждым элементом справа от него пока он не
окажется в крайне правой позиции. На втором
проходе помещаем второй максимальный
элемент в предпоследнюю позицию и так далее.
Пузырьковая сортировка работает также как
и сортировка выбором, хотя она и делает
гораздо больше работы на то, чтобы
переместить элемент в его конечную позицию.
Характеристики Простейших Сортировок
Свойство 1 Сортировка выбором
использует около N2/2 сравнений и N обменов.
Свойство 2 Сортировка вставкой
использует около N2/4 сравнений и N2/8 обменов
в среднем, и в два раза больше в наихудшем
случае.
Свойство 3 Пузырьковая
сортировка использует около N2/2 сравнений и
N2/2 обменов в среднем и наихудшем случаях.
Свойство 4 Сортировка вставкой
линейна для "почти сортированных"
файлов.
Свойство 5 Сортировка выбором
линейна для файлов с большими записями и
маленькими ключами.
Итак, на сегодняшнем занятии мы ознакомились с элементарными методами сортировки.
