end.
По структуре программы видно, что такая сортировка требует (N-1)(N-1) операций. То есть время работы программы можно оценить как O(N2).
Приведем пару соображений по оптимизации написанного кода. Представим себе, что у нас есть массив на два миллиона чисел, и мы уже сделали миллион проходов. Это значит, что как минимум миллион чисел в массиве уже стоят на своих законных местах в конце массива. Следовательно, нет никакого смысла проходить правую половину массива, потому что там никаких изменений точно уже не будет. Итак, если на первом проходе мы делаем N-1 сравнение, то на втором достаточно N-2, на третьем - N-3 и так далее по мере увеличения количества чисел, которые стоят на своих местах. Таким образом кусочек программы, отвечающий за сортировку можно переписать так:
for i:=1 to N-1 do {по проходам}
for j:=1 to N-i do {по парам элементов}
if a[j]>a[j+1] then begin {если в паре левый элемент больше правого}
temp:=a[j]; {меняем их местами}
a[j]:=a[j+1]; {если нет, то просто переходим к следующей}
a[j+1]:=temp;
end;
Как видите, изменился ровно один символ. В первом цикле разность N-1 заменена разностью N-i. Однако, количество операций (а вместе с ним и время работы) нам удалось сократить вдвое. Это легко увидеть, если нарисовать следующий график:
Площадь закрашенного треугольника будет как раз представлять количество сравнений. А треугольник есть ничто иное как половинка квадрата со стороной (N-1). Хотя, следует признать, что оценка времени работы алгоритма все еще составляет O(N2).
Второе соображение для оптимизации метода простого обмена основано на таком утверждении: если за полный проход в массиве не сделано ни одной перестановки, то его можно считать отсортированным. Что значит «не сделано ни одной перестановки»? Это значит, что все пары соседних чисел расположены «правильно», то есть большее число идет позже меньшего, поэтому они в перестановках не нуждаются. Это позволяет значительно сократить время в случаях, когда более или менее повезло с исходными данными.
Например, в массиве 8, 1, 2, 3, 4, 5, 6 будет вообще достаточно одного прохода, чтобы вытолкнуть восьмерку на последнее место.
Существенных изменений в структуре программы не будет – как был двойной цикл, так и остался. Просто внешний цикл будет заменен на цикл с условием. Программа в этом случае может выглядеть, например, так:
const
N=100;
var
a : array [1..N] of Integer;
i, j : integer;
temp : integer;
flag : boolean; {признак того случались ли перестановки}
begin
{ввод массива}
i:=0;
repeat
inc(i); {проходы будем считать, чтобы не все из них}
flag:=false; {делать до конца. перед проходом сбросим}
for j:=1 to N-i do {признак того, что перестановки были.}
if a[j]>a[j+1] then begin {если в паре левый элемент больше правого}
temp:=a[j]; {меняем их местами}
a[j]:=a[j+1]; {если нет, то просто переходим к следующей}
a[j+1]:=temp;
flag:=true; {если была перестановка – установим признак}
end;
until not(flag);
{массив упорядочен и готов к использованию}
end.
Стоит заметить, что в худшем случае (а именно, если на входе дан массив, упорядоченный в другую сторону) время работы все равно будет составлять O(N2) и по количеству операций сравнения программа не будет отличаться от предыдущего примера.
Обмен с убывающими смещениями
Сразу оговоримся, что существует такой вариант исходных данных, при которых данный метод будет работать за время O(N2). Однако, в среднем случае этот метод способен дать значительный выигрыш по времени по сравнению с методом простого обмена.
Заметим следующее: каждый проход метода простого обмена способен сместить элемент массива не более чем на одну позицию влево. Поэтому, наибольшее время займет работа метода простого обмена в случаях, когда наименьший элемент находится на последнем месте. В методе обмена с убывающими смещениями добавляются несколько первых шагов, цель которых при необходимости поменять местами элементы, находящиеся друг от друга на расстоянии большем единицы. То есть поместить числа по возможности поближе к их окончательным позициям в массиве. Тогда количество шагов для метода простого обмена значительно сократится.
Итак, давайте рассмотрим работу этого метода на примере. Пусть дан массив из 8 чисел, который требуется упорядочить по возрастанию:
4 | 6 | 8 | 2 | 5 | 0 | 1 | 7 |
Выберем шаг d=[N/2] (в какую сторону округлять, в принципе не очень важно, обычно размеры массивов таковы, что на фоне тысяч элементов единичка при округлении как-то не замечается).
В нашем примере шаг будет равен d=[8/2]=4.
На первом проходе будем сравнивать пары элементов массива, расположенные на расстоянии d. В нашем примере это будут 1-й и 5-й, 2-й и 6-й, 3-й и 7-й, 4-й и 8-й. Как и ранее, в методе простого обмена, если расположение элементов в паре нас не устраивает – будем менять их местами. Покажем подробно первый проход:
4 | 6 | 8 | 2 | 5 | 0 | 1 | 7 |
Шаг 1. Сравнить числа 4 и 5. Местами менять не будем.
4 | 6 | 8 | 2 | 5 | 0 | 1 | 7 |
Шаг 2. Сравнить числа 6 и 0. Поменять местами, чтобы большее стояло правее. Расположение чисел в массиве станет таким:
4 | 0 | 8 | 2 | 5 | 6 | 1 | 7 |
4 | 0 | 8 | 2 | 5 | 6 | 1 | 7 |
Шаг 3. Сравнить числа 8 и 1. Поменять местами. Теперь в массиве числа будут расположены так:
4 | 0 | 1 | 2 | 5 | 6 | 8 | 7 |
4 | 0 | 1 | 2 | 5 | 6 | 8 | 7 |
Шаг 4. Сравнить числа 2 и 7 и оставить их на своих местах.
После такого подготовительного прохода элементы массива расположены довольно близко к тем местам, которые они должны занять после сортировки. По крайней мере все «большие» элементы находятся в правой половине, все «маленькие» - в левой. Конечно, так будет далеко не всегда, но в среднем случае такие подготовительные действия могут быть очень полезны.
Далее, если d>1, то d уменьшаем в 2 раза и делаем еще один проход. Теперь будем сравнивать числа, находящиеся на расстоянии 2: 1-е и 3-е, 2-е и 4-е, 3-е и 5-е, 4-е и 6-е, 5-е и 7-е, 6-е и 8-е.
После первого прохода массив был таким:
4 | 0 | 1 | 2 | 5 | 6 | 8 | 7 |
Разберем второй проход пошагово:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
