Сортировка и бинарный поиск
Задача сортировки
Очень часто на практике возникает задача переупорядочивания элементов по различным признакам. Наличие определенного порядка вполне естественно для многих объектов и часто используется, например: в школьном журнале ученики отсортированы по фамилии, на уроке физкультуры все становятся в строй, отсортированный по росту, в интернет магазинах мы видим товары, отсортированные по цене.
Следовательно, возникает задача упорядочивания элементов по заданному признаку. В дальнейшем мы будем рассматривать алгоритмы сортировки массивов чисел, однако рассмотренные алгоритмы используются также и при сортировке прямых, строк и прочих объектов. На самом деле для большинства алгоритмов абсолютно не важно, что именно сортировать, надо только уметь сравнивать два объекта между собой, и определять какой их больше, а какой меньше.
Мы уже говорили, что при анализе алгоритмов основной характеристикой является их асимптотика. Далее будем считать, что мы сортируем массив чисел А, в котором N элементов. Тут будут рассматриваться алгоритмы с асимптотикой O(N2), которые носят больше теоретическое значение, так как являются довольно медленными. Алгоритмы с асимптотикой O(N*log N), которые являются оптимальным в плане скорости выполнения, и которые чаще используются на олимпиадах.
Сортировка методом простого выбора
Метод состоит в следующем: находится минимальный элемент массива и меняется местами с первым элементом массива. Потом находится минимальный элемент массива, без учета первого элемента, и меняется местами со вторым элементом и так далее. На каждом шаге мы будем искать минимум в оставшейся части массива и ставить его на нужное место. Реализация:
for i:=1 to N-1 do begin {позиция, на которую будем ставить элемент }
min:=i; {инициализация индекса минимального элемента}
for j:=i+1 to N do {поиск минимального элемента}
if a[min]>a[j] then min:=j; {проверка на минимальность }
t:=a[i];a[i]:=a[min];a[min]:=t; {ставим на позицию i минимальный найденный элемент}
end;
Очевидно, что время работы алгоритма O(N2).
Пузырьковая сортировка
Данный алгоритм назван так по той причине, что его действия напоминают действия пузырьков, всплывающих на поверхность. В этом алгоритме мы просто будем сравнивать два соседних элемента и менять их местами, если это необходимо:
repeat
canExit:=true; {Пока неупорядоченных пар не было}
for i:=1 to N-1 do {Просматриваем все пары соседних элементов}
begin
if a[i]>a[i+1] then {если элементы стоят в неверном порядке}
begin
canExit:=false; {нашли неупорядоченную пару}
t:=a[i];a[i]:=a[i+1];a[i+1]:=t; {Меняем местами элементы }
end;
end;
until canExit; {пока не дойдем до итерации, когда неупорядоченных пар не будет}
Каждый проход цикла for проверяет все соседние элементы на правильность их расположения. Если они стоят в неверном порядке – то элементы меняются местами. Если же мы дошли до такой итерации, что ни одного обмена не было выполнено, значит, все пары соседних элементов стоят в правильном порядке, а из этого следует, что массив уже отсортирован и больше никаких действий можно не производить.
В худшем случае внешний цикл будет выполнен N раз и общее время выполнения составит O(N2).
Пирамидальная сортировка
Начиная с этого пункта, мы будем рассматривать сортировки со временем работы O(N*log N). Самой простой пожалуй является пирамидальная сортировка, которая использует структуру данных куча(рассмотрена во втором модуле). Напомню, что у кучи есть операции:
Insert(key): вставка элемента в множество с заданным ключом key.
ExtractMin(): извлечение элемента из очереди с минимальным ключом.
Причем каждая их этих операций выполняется за время O(log N). Напрашивается очень простой алгоритм:
1) Добавить все N элементов в кучу
2) N раз извлечь минимум(извлекаемые элементы будут находится в отсортированном порядке)
Каждый их этих шагов требует O(N*log N) операций, значит, в сумме потребуется также O(N*log N) операций. К плюсам этого алгоритма можно отнести то, что он является очень простым в плане понимания и реализации. Минусы: требует знания кучи, работает немного медленнее алгоритмов, рассматриваемых ниже.
Сортировка слиянием
Для понимания данного алгоритма рассмотрим следующую задачу: у нас имеется два отсортированных массива размера N, требуется получить по ним массив размера 2N, состоящий из элементов обоих массивов. Очевидно, что можно просто выписать два этих массива в один размера 2N и просто отсортировать получившейся массив, но этот алгоритм не будет оптимальным с точки зрения асимптотики.
Алгоритм, эффективно решающий данную задачу называется алгоритмом слияния и работает он за время O(N). Суть алгоритма: изначально выберем в качестве текущих первые элементы обоих массивов. Потом на каждом шаге мы будем выбирать минимальный из текущих элементов массивов, дописывать его в результирующий массив и сдвигать использованный индекс на единицу.
Сам алгоритм состоит из трех этапов:
1) Сортируемый массив разбивается на две части примерно одинакового размера;
2) Каждую из получившихся частей сортируем отдельно тем же самым алгоритмом;
3) Два отсортированных массива соединяем в один отсортированный при помощи алгоритма слияния.
Приведу свою реализацию:
Procedure Merge(l, m,r:Longint); //Метод слияния
Var i, j,n1,n2,k:Longint;
begin
n1:=m-l+1;
n2:=r-m;
for i:=1 to n1 do left[i]:=a[l+i-1];
for i:=1 to n2 do right[i]:=a[m+i];
Inc(n1); left[n1]:=inf;
Inc(n2); right[n2]:=inf;
i:=1; j:=1;
for k:=l to r do begin
if left[i]<=right[j] then // находим минимальный из текущих элементов
begin a[k]:=left[i]; Inc(i) end else //сдвигаем использованный индекс на 1
begin a[k]:=right[j]; Inc(j); end;
end;
end;
Procedure Sort(l, r:Longint); //Сортирует элементы с l по r в массиве А
var m:Longint;
begin
if l=r then exit; //если размер массива равен единице – то сортировать не надо
m:=(l+r) div 2; //делим на две части
Sort(l, m); //сортируем левую
Sort(m+1,r); //сортируем правую
Merge(l, m,r); //сливаем обе отсортированные части в одну
end;
Довольно необычным может показаться вызов метода Sort из самого метода, но на самом деле это очень распространенный прием, который называется рекурсией (вызов функции из неё же самой). Дальше мы будем рассматривать много рекурсивных алгоритмов, поэтому будет очень полезно разобраться и проанализировать порядок выполнения действий в рекурсивных функциях и процедурах.
Время работы данного алгоритма O(N*log N).
Быстрая сортировка
Данный алгоритм получил свое название в силу того, что он очень быстро работает на практике, за счет чего в большинстве случаев и используется. Алгоритм также является рекурсивным и состоит из следующих шагов:
1) выбрать опорный элемент
2) сравнить все остальные элементы с опорным и разбить массив на три части — меньшие опорного, равные и большие, расположить части в порядке меньшие-равные-большие(при этом между собой «большие» и «меньшие» еще не упорядочены).
3) повторить алгоритм рекурсивно для «меньших» и «больших».
Реализация алгоритма:
Procedure Qsort(l, r:Longint); //сортировка части массива А с l по r
var i, j,x, m:Longint;
begin
m:=a[(l+r) div 2]; //выбор среднего элемента в качестве опорного
i:=l;
j:=r;
repeat //сравнение с опорным и переупорядочивание
while a[i]<m do Inc(i);
while a[j]>m do Dec(j);
if i<=j then begin
x:=a[i]; a[i]:=a[j]; a[j]:=x;
Inc(i); Dec(j);
end;
until i>j;
if l<j then Qsort(l, j); //рекурсивный вызов для сортировки «меньших»
if i<r then Qsort(i, r); //рекурсивный вызов для сортировки «больших»
end;
Заметим, что есть несколько методик выбора опорного элемента, однако чаще всего берут средний, как в указанной реализации. Время работы алгоритма в среднем O(N*log N), причем на практике алгоритм работает быстрее остальных рассмотренных. Однако заметим, что максимальная скорость достигается в ситуации, когда количество «меньших» и «больших» примерно одинаково. А в худшем случае опорный элемент будет самым большим либо самым маленьким, и тогда в «меньшие» попадет почти весь массив, а множество «большие» будет пустым, либо наоборот. Таким образом, в худшем случае время выполнения алгоритма будет O(N2).
Бинарный поиск
Пожалуй, одним из самых распространенных алгоритмов на олимпиадах является алгоритм бинарного поиска (его еще называют методом двоичного поиска или дихотомией). Суть метода очень проста: если мы ищем элемент на каком-то отрезке, и за один запрос мы можем узнать, находится ли элемент, который мы ищем, на указанной нами части отрезка – то выгоднее всего делить отрезок поиска на две равные части.
Пример: пусть нам надо угадать число от 1 до 100, причем мы можем спрашивать у ведущего про определенное число, на что он нам будет отвечать «Вы угадали», «больше» или «меньше». Чтобы минимизировать количество вопросов ведущему самой выгодной будет следующая стратегия:
1) Находим середину текущего интервала поиска(на первом шаге 50)
2) Загадываем ведущему число, найденное на первом шаге
3) Если число еще не угадано - то изменяем наш интервал поиска в необходимом направлении (то есть если на запрос 50 нам ответили «меньше» - то наш интервал поиска становится от 1 до 49, и на следующем ходу мы загадаем 25, если «больше» - то интервал поиска станет от 51 до 100 и на следующем ходу мы загадаем 75).
Данный алгоритм хорошо тем, что после каждого шага наш интервал будет уменьшаться в два раза. А это значит, что для угадывания числа от 1 до N нам потребуется всего лишь log N вопросов ведущему. Например, чтобы угадать число от 1 до миллиарда понадобится всего 30 вопросов. Аналогичный подход применяется во многих алгоритмах. Рассмотрим классическую задачу поиска элемента в отсортированном массиве.
Пусть мы ищем элемент Х в отсортированном массиве А:
Procedure BinarySearch;
Begin
L := 1; //границы интервала поиска
R := N;
While R <> L Do
If A[(L + R) Div 2] = X Then //нашли элемент
Break
Else Begin
If A[(L + R) Div 2] < X Then
L := (L + R) Div 2 + 1 //сдвигаем левую границу
Else
R := (L + R) Div 2; //сдвигаем левую границу
End;
If A[(L + R) Div 2] = X Then P := (L + R) Div 2 Else P := 0;
End;
После окончания работы алгоритма в Р будет находиться номер позиции элемента Х, если он есть в массиве, или 0, если его в массиве нет.
Литература:
1) Д. Кнут «Искусство программирования. Т. 1 Основные алгоритмы».
2) Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ».
3) www. wikipedia. org
