В процессе анализа попытаемся ответить на несколько вопросов:
• Насколько хороши разработанные алгоритмы?
• Как улучшить имеющиеся алгоритмы и программы?
• Эффективна ли программа с точки зрения затрат времени и памяти?
• Какие ограничения можно ввести, чтобы улучшить алгоритм?
Идея сортировки методом простой вставки не сложная: считается, что перед рассмотрением элемента a[i] предыдущие элементы a[1], a[2], ..., a[i-1] уже упорядочены, и подбирается место для a[i] записи.
Сортировка массива начинается со второй записи. На i-м шаге a[i] сравнивается по очереди с a[i-1], a[i-2],... до тех пор, пока выполняется условие a[i] < a[j] ( j = i-1,i-2, ... ), или достигнут левый конец упорядоченного подмассива ( j = 1, a[i] < a[1] ). Выполнение условия a[i] >= a[j] означает, что запись a[i] нужно вставить между a[j] и a[j+1]. Тогда записи a[j+1], a[j+2], ..., а[i-1] сдвигаются на одну позицию, и запись a[i] помещается в позицию j+1. На каждом шаге отсортированная часть массива увеличивается. Сортировка закончится на N-1 шаге, если в массиве N элементов.
Программа сортировки может выглядеть так:
Procedure Sort;
var i, j :integer;
Begin
For i := 2 to N do Begin
j := i;
While ( j > 1 ) and ( a[j] < a[j-1] ) do Begin
Swap(a[j], a[j-1]);
Dec(j);
end;
end;
end;
Массив a опишем так:
Type mas = array[1..N] of integer;
Var a: mas;
Процедура Swap содержит следующие операторы присваивания:
t : = a[j];
a[j] := a[j-1];
a[j-1] := t;
Обратим внимание на переменную t в процедуре Swap, в нее каждый раз посылается одно и то же значение – то, которое было в начальный момент в ячейке a[j]. Поэтому из первого варианта программы можно убрать процедуру Swap и изменить оператор сравнения.
Procedure Sort;
var i, j, t : integer;
Begin
For i := 2 to N do Begin
j:= i;
t:= a[j];
While (j > 1) and (a[j-1] > t) do Begin
a[j]:= a[j-1];
Dec(j);
end;
a[j]:= t;
end;
end;
Попробуем поэкспериментировать со вторым условием в цикле: While (a[j-1] > t). Изменим это условие на a[j-1]>=t.
На первый взгляд программа работает также, но мы будем лишний раз заходить в цикл While и менять местами одинаковые элементы. Наша модификация не улучшит работу программы, значит, оставим это условие без изменений. Если записи с одинаковыми ключами не меняются местами, говорят, что сортировка устойчивая. Сделаем вывод, что при правильном написании программного кода, сортировку методом простой вставки можно назвать устойчивой.
Ещё раз взглянем на предыдущий вариант процедуры. Нужна ли нам переменная t? При использовании t происходит бесполезная трата времени на её запоминание и последующее чтение с целью обмена значениями.
Чтобы избавиться от ненужной переменной изменим наш массив А, сделав его типом array[0..N] of integer.
Рассматриваемый i-ый элемент теперь будет записываться на нулевое место и играть роль «барьера». Изменить процедуру простой вставки на процедуру с барьерным элементом очень просто.
В общем случае время выполнения алгоритма пропорционально количеству операций сравнения (a[j-1] > t) и числу перемещений элементов по массиву (тело цикла While).
У нас в массиве N элементов. Основной цикл (For i:=…) идет от 2 до N. Второй цикл (While) идет от i по убывающей до единицы. В худшем случае самый маленький элемент стоит на последнем, N-ом, месте в массиве. Значит, надо сделать N-1 сравнение и перемещение, чтобы поставить элемент на свое (первое) место. Получается, что в худшем случае, сортировка находится в квадратичной зависимости от числа элементов массива, то есть С = О (N2).
Изменения, которые были сделаны, незначительны. Но для небольших массивов и этих модификаций будет достаточно: подобные массивы отсортируются быстро. Этот метод также эффективен, когда записи частично упорядочены, т.е. записи находятся недалеко от своих конечных положений.
Когда при сортировке методом простых вставок обрабатывается i-й элемент, его нужно сравнить в среднем примерно с i /2 ранее отсортированными элементами.
При больших N этих сравнений получается слишком много. Поэтому в 1946 году Джон Мочли (John Mauchly) предложил метод бинарных вставок, чтобы сократить число сравнений.
Этот способ основывается на том факте, что мы вначале ищем место, куда нужно вставить элемент, а затем уже вставляем его. Это дает существенный выигрыш по числу сравнений.
Поскольку все элементы массива перед записью a[i] уже упорядочены, то можно использовать более эффективный метод поиска места для a[i]. В данном случае это алгоритм бинарного поиска. Например, если вставляется 64-я запись, то можно сравнить ее с 32-й, и если 64-я запись окажется меньше, то сравнить ее уже с 16-й, а если окажется больше, то сравнить с 48-й и т.д. Таким образом, место 64-й записи будет определено в худшем случае за шесть сравнений.
Для реализации этого алгоритма, кроме основной процедуры, нам потребуется вспомогательная (Change ()), которая будет находить место в массиве для нового элемента. Логика поиска нужного места такая же, как в методе простой вставки.
Основная процедура сортировки может выглядеть так:
Procedure Sort;
var i,j,r,m:integer;
Begin
m:=1;
For i:=2 to N do Begin
If a[i]
While r-j>1 do Begin
m:=(r+j) div 2;
If a[m]>a[i] then r:=m
else j:=m;
end;
If (a[m]>a[i]) then
If (a[m-1]>a[i]) and (m<>1) then Change(a,i,m-1)
else Change(a,i,m)
else Change(a,i,m+1);
end;
end;
end;
Зачем нам в основной процедуре условие
If (a[m-1]>a[i]) and (m<>1) then… ?
Попробуем обойтись без него и запишем последнее условие так:
…
If (a[m]>a[i]) then Change(a,i,m-1)
else Change(a,i,m+1);
…
С таким условием программа будет работать примерно в половине случаев. Все будет зависеть от того, как мы подберем элементы массива.
Если первый элемент больше второго, их необходимо поменять местами. И менять мы будем сначала второй элемент с первым, а потом получится, что надо будет поменять первый с нулевым, таким образом, мы выйдем за пределы массива. Программа будет работать неправильно.
Может возникнуть ещё один вопрос: может быть, при условии, что a[m]>a[i] вызывать процедуру Change(a, i, m)? Но при таком условии первый элемент всегда будет оставаться на своём месте, не меняясь ни при каких обстоятельствах.
Метод бинарных вставок решает временную проблему лишь наполовину. Когда мы находим место для i-го элемента, нам все равно приходится делать перестановки. Время, которое мы тратим на перестановки так и остается О(N), как и в методе простых вставок. Зато вполовину уменьшается число сравнений, то есть «отсеивается» половина данных, что займет O(lg N) времени. Получается, что сортировка бинарными вставками работает за время, пропорциональное N*Lg N.
Так как число перестановок остается по-прежнему достаточно большим, Х. Неглер (H. Negler) показал, что метод бинарных вставок не рекомендуется использовать при сортировке более N=128 элементов, так как с ростом N зависимость от N2 начнет преобладать.
Чтобы исправить недостаток сортировки бинарными вставками, необходим метод, в котором элементы перемещаются большими скачками. Такой метод предложил Д. Шелл (D.Shell) в 1959 году.
Идея состоит в обмене элементов, расположенных не только рядом, как в алгоритме простых вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов. Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап - 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Выполняется сортировка в каждой четверке. Следующий этап - 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом простых вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных "дальних" обменов.
Процедуру этой сортировки для приращений 8-4-2-1 можно реализовать так:
Procedure Sort;
var i, j, k, up, t, help :integer;
Begin
k:=n div 2;
While k>0 do Begin
up:=n-k;
repeat
t:= 0;
For i:= 1 to up do
If a[i]>a[i+k] then Begin
help:=a[i];
a[i]:=a[i+k];
a[i+k]:=help;
t:=i;
end;
up:=t-k;
Until t = 0;
k:=k div 2;
end;
end;
Если изменить условие a[i] > a[i+k] на a[i] >= a[i+k]? В этом условии мы меняем местами элементы, если a[i+k] больше a[i]. Значит, при изменении условия, у нас будут меняться местами одинаковые элементы. Такое условие не принесет никакой пользы.
Хотя этот метод легко объяснить, его формальный анализ довольно труден. До сегодняшнего момента никому не удалось выполнить точный анализ алгоритма. Временная оценка сортировки зависит от выбранной последовательности шагов. Но пока также не удалось определить и наилучшую последовательность. Д. Кнут описал математические исследования, по которым временная оценка алгоритма близка к N1,25.
Ещё одним важным этапом улучшения программы является подбор подходящих структур данных. Выбор «правильных» структур данных позволит избежать ненужных операций. Связный список прекрасно подходит для реализации сортировки методом простых вставок. Так как мы просматриваем элементы в одном направлении, можно использовать список с однонаправленной связью. Чтобы вставить элемент на своё место, надо просто изменить несколько связей.
Рекомендации по выбору правильного метода сортировки.
Мы рассмотрели несколько видов сортировок. Необходимо уметь выбирать правильные методы для конкретной задачи. Ниже приведено несколько рекомендаций по выбору метода сортировки:
* Если сортируется небольшой объем данных (N < 100), то рекомендуется выбирать простой метод сортировки, так как сложные алгоритмы имеют сложный код и не эффективны при малом количестве сортируемых элементов.
* Если сортируются элементы большого размера, то рекомендуется использовать специальные таблицы, с помощью которых осуществляется доступ к самим элементам (например, это могут быть указатели на элементы или их порядковые номера), причем ключ, по которому сортируются данные, может входить или не входить в данные такой таблицы. После сортировки таблицы можно или переставить исходные данные по таблице, или оставить все как есть и осуществлять дальнейший доступ к данным по уже отсортированной таблице.
* Если сортируются данные в файле, то необходимо учитывать, что большая часть времени будет тратиться на чтение, запись элемента и перемещение по файлу. В такой ситуации методы вставок являются не эффективными, так как требуют большое число перестановок.
* Если используются структуры данных, отличные организацией доступа от массива, то необходимо выбирать метод сортировки наиболее подходящий для данной структуры.
* Рекомендуется выбирать алгоритм сортировки с учетом предполагаемого входного состояния данных (является таблица частично отсортированной, отсортированной в обратном порядке и т.д.).
Список литературы
1. Д. Бентли. Жемчужины творчества программистов.
М., «Радио и связь», 1990.
2. Б. Керниган, Р. Пайк. Практика программирования
С.-Петербург, «Невский диалект», 2000.
3. Д. Кнут. Искусство программирования. Том 3. Сортировка и поиск.
Москва, Санкт-Петербург, Киев, 2001.
4. Окулов С.М., Пестов А.А.. 100 задач по информатике.
Киров, 2000.
5. Окулов С.М.. Основы программирования. М.:?????, 2002.
6. Р. Седжвик. Фундаментальные алгоритмы на С++. Части 1-4.
Москва, Санкт-Петербург, Киев, 2001.
7. А. Г. Юркин. Задачник по программированию.
Санкт-Петербург, «Питер», 2002.
Самые свежие известия об аддоне WoW Катаклизм из первых уст с мероприятия Близзкон. Такого никогда еще не было
