вторник, 11 июня 2013 г.

Еще раз об алгоритмах сортировки

Часто возникает ситуация написать какую-нибудь сортировку, но как назло - просто не можешь вспомнить как правильно расставить параметры цикла, что с чем сравнивать и что переставлять. Приведу пример одного такого неправильного алгоритма:

for i:=1 to n-1 do
for j:=i+1 to n do

  if a[j]>a[j-1] then begin  temp:=a[j];a[j]:=a[j-1];a[j-1]:=temp; end;

Как же написать алгоритм сортировки "с нуля" и правильно? Для этого нужно знать как они работают. Все сортировки упорядочивают элементы массива по возрастанию или по убыванию их значений. Пусть у нас есть массив целых  чисел (но может быть и действительных чисел и символов и строк и всё, что можно выразить в виде битов и байтов). Обозначим его за "A". Количество элементов в массиве пронумерованы от 1 до n .
Рассмотрим все известные алгоритмы сортировки:
- обменная (пузырек и челнок),
- выбором,
- вставками.
Все остальные (Шелла, Хоара и т.д.) основаны на них.

Сортировка пузырьком (часто применяемая). Она означает, по аналогии образования пузырьков в кипящей воде, что более легкий по весу пузырек (элемент массива) всплывает снизу на поверхность воды. Так в массиве это "более легкий" (наименьший элемент ) передвигается от начала к концу массива.
Рассмотрим на примере для n=5. Если было: 2, 0, 1, 5, 3 - то 0, как более "легкий", переместится в конец: 2, 1, 5, 3, 0. При этом идет сравнение двух рядом стоящих элементов массива (пара чисел), т.е. если на i-м месте элемент меньше рядом стоящего (If A[i]<A[i+1]), то меняем их местами. Начинаем с самого первого места и до предпоследнего (если брать последний, то следующего не будет!). Запишем это с помощью цикла с параметром for:
for i:=1 to 4 do
  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
  end;
Маленькое отступление:
Отдельный вопрос: как запомнить перестановку, т.к. простое переприсваивание
A[i]:=A[i+1]; A[i+1]:=A[i];
не работает! Перестановку легко запомнить, если представить, как собирают два вагона с помощью паровоза и двух путей. В начале каждый вагон размещены по разным путям:
1 путь - вагон A[i];
2 путь - вагон A[i+1];
Затем паровоз (temp) забирает с 1-го пути вагон A[i] (Temp:=A[i];). Далее, со 2-го пути прицепляет в конец вагон A[i+1] (A[i]:=A[i+1];). При этом паровоз движется на 2-й путь "задом", т.е. со стороны прицепленного вагона A[i]. Затем возвращаем паровоз temp в конец, т.е. прицепляемся к вагону A[i+1] с конца (A[i+1]:=temp;). Может быть не совсем логично, но если сразу вспомнить о "вагончиках", которые "следуют" один за другим, то сразу правильно запишешь перестановку.
Или еще пример: нужно переложить деньги из одного кошелька в другой. Здесь двумя руками не обойдешься, нужен кто-то, кому в начале отдаешь деньги на "временное хранение" (Temp:=A[i];), затем перекладываешь из другого кошелька другую сумму денег (A[i]:=A[i+1];), затем забираешь деньги у товарища и кладешь эту сумму во второй кошелек (A[i+1]:=temp;).
Можно придумать еще кучу таких же приемов для запоминания.

Итак, вернемся к сортировке. Мы переставили только один элемент. Далее, из оставшихся более легкий (1) перемещается на предпоследнее место:
for i:=1 to 3 do

  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
  end;
Получим: 2, 5, 3, 10


Точно также переместим следующий минимальный элемент (2).

for i:=1 to 2 do

  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
  end;
Получим: 5, 3, 210



Осталось проверить только одну пару чисел: 5 и 3, но они уже и так стоят на месте, но цикл все таки нужно написать для общего случая (потом мы немного изменим алгоритм, чтобы он не делал лишние перестановки):

for i:=1 to 1 do

  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
  end;

Что можно заметить? Тело цикла не изменяется, но изменяется конечное значение параметра цикла от 4 до 1 (эти числа выделены зеленым цветом). Можно заметить, что для 5 элементов цикл повторяется 4 раза, если элементов будет 6, то цикл повторится 5 раз, и т.д. Если это записать через переменную n - количество элементов (в нашем случае n=5), то получим следующие выражения:
4=n-1
3=n-2
2=n-3
1=n-4

Видно, что в выражениях изменяется вычитаемое - от 1 до 4 (это значение можно изменять в цикле по параметру, например, k). Тогда наше конечное значение для цикла по параметру i можно записать как n-k, где k является параметром внешнего цикла и изменяется от 1 до 4:
for k:=1 to 4 do
 for i:=1 to n-k do

  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
  end;
Или в общем случае для любого n (запишем 4 как n-1):
for k:=1 to n-1 do
 for i:=1 to n-k do

  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
  end;
Если добавить переменную-флаг (например, F типа boolean) , которая будит сигналить о том, была перестановка или нет (вначале f:=true; затем в блоке then, когда переставляем элементы массива изменим значение на false), то алгоритм будет работать быстрее.

for k:=1 to n-1 do begin
 f:=true; //считаем, что массив отсортирован (гипотеза)
 for i:=1 to n-k do

  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
     f:=false;//если это не так, то произойдет перестановка
  end;
  if f then break;//если гипотеза подтвердилась, то выходим из цикла (команда break;)
end;
Вместо логической переменной можно использовать целое значение 0-false, 1-true.
Иногда эту сортировку записывают с помощью цикла While или Repeat:
k:=n-1;
repeat
 f:=true;
for i:=1 to k do

  if (A[i]<A[i+1]) then begin
    Temp:=A[i]; A[i]:=A[i+1]; A[i+1]:=Temp;
     f:=false;
  end;
k:=k-1;
until f;
 

По аналогии рассмотрим алгоритм выбором на том же исходном массиве. Алгоритм заключается в следующем: выбираем наименьший элемент и ставим его на первое место.
Далее, ищем следующий наименьший и ставим его на второе место и т.д. Эту операцию можно представить, если вспомнить как вы переставляли книжки на полке по алфавиту авторов книг или по размеру книг. Так как книги обычно на полке стоят достаточно плотно, то вы вначале определяете какую книгу нужно вытащить и поставить на первое место (в этом случае вы первую книгу не возвращаете на место вынутой, но если поставить такое условие, то это аналог нашей сортировки).
Итак, было: 2, 0, 1, 5, 3. Здесь 0 - наименьший элемент и он стоит на втором месте (это важно, так как при перестановке элементов массива нужно знать не значения, а их индекс, т.е. местоположение).
Запишем алгоритм поиска минимума с использованием этого индекса (обозначим его за mini). Предположим, что минимальный элемент стоит на первом месте (mini:=1), тогда сравниваем его со вторым (if A[mini]>A[2] then), если второй меньше первого, то заменим индекс на 2 (mini:=2). Далее сравним также третий (if A[mini]>A[3] Then), четвертый и т.д. Видно, что в нашем алгоритме будет меняться только индекс сравниваемого элемента от 2 до 5. Запишем в виде цикла:
mini:=1;
for i:=2 to 5 do
 if A[mini]>A[i] then imin:=i;
После найденного номера минимального элемента запишем перестановку его с первым элементов, т.е. A[1] меняем с A[mini] (вспоминаем вагончики), и запишем:
temp:=A[1];A[1]:=A[mini];A[mini]:=temp;
Можно перед этим проверить, изменился ли номер mini:
if mini<>1 then begin temp:=A[1];A[1]:=A[mini];A[mini]:=temp; end;
Получим массив:  0, 2, 1, 5, 3.
Теперь начнем поиск минимума со второго элемента:

mini:=2;
for i:=3 to 5 do
 if A[mini]>A[i] then imin:=i;
Переставим найденный минимум на второе место:
if mini<>2 then begin temp:=A[2];A[2]:=A[mini];A[mini]:=temp; end;
Получим массив:  0, 1, 2, 5, 3.
С двойкой, которая стоит на 3-ем месте, мы ничего не поменяем, но в общем случае придется повторить поиск и замену: 
mini:=3;
for i:=4 to 5 do
 if A[mini]>A[i] then imin:=i;
if mini<>3 then begin temp:=A[3];A[3]:=A[mini];A[mini]:=temp; end;
Получим массив:  01, 2, 5, 3.
Каждый раз я копировала фрагмент программы и исправляла несколько чисел (они выделены зеленым цветом). Как и с сортировкой пузырьком можно оформить внешний цикл с параметром k от 1 до 4:

for k:=1 to 4 do begin
mini:=k;
for i:=k+1 to 5 do
 if A[mini]>A[i] then imin:=i;
if mini<>k then begin temp:=A[k];A[k]:=A[mini];A[mini]:=temp; end;
end;
В общем случаем для любого размера n получим:
for k:=1 to n-1 do begin
mini:=k;
for i:=k+1 to n do
 if A[mini]>A[i] then imin:=i;
if mini<>k then begin temp:=A[k];A[k]:=A[mini];A[mini]:=temp; end;
end;
 
Разберем сортировку вставками. Предположим, что первый элемент стоит на месте, т.е. массив из одного элемента всегда считается отсортированным. Будем добавлять к этому массиву по одному элементу так, чтобы новый элемент сразу вставал на свое место, не изменяя свойство отсортированности массива. Если условие возрастания не выполняется, то переставляем первый и второй элемент: было 2, 0, 1, 5, 3; получим 0, 2, 1, 5, 3.
i:=1;
if a[1]>a[2] then begin
temp:=a[1]; a[1]:=a[2]; a[2]:=temp;
end;
Далее подставляем третий элемент (1), сравнивая сначала со вторым, а затем с первым элементом:
if a[2]>a[3] then begin
temp:=a[2]; a[2]:=a[3]; a[3]:=temp;
end;
if a[1]>a[2] then begin
temp:=a[1]; a[1]:=a[2]; a[2]:=temp;
end;Второе условие не выполнится и перестановки не будет. Получим 0, 1, 2, 5, 3
В следующий раз добавляем число 5 в наш массив, но он уже стоит на месте и в перестановке не нуждается.
if a[3]>a[4] then begin
temp:=a[3]; a[3]:=a[4]; a[4]:=temp;
end;
if a[2]>a[3] then begin
temp:=a[2]; a[2]:=a[3]; a[3]:=temp;
end;
if a[1]>a[2] then begin
temp:=a[1]; a[1]:=a[2]; a[2]:=temp;
end;
А вот число 3 потребует только одной перестановки с числом 5. Получим: 0, 1, 2, 3, 5.- и наш массив уже отсортирован.
if a[4]>a[5] then begin
temp:=a[4]; a[4]:=a[5]; a[5]:=temp;
end;
if a[3]>a[4] then begin
temp:=a[3]; a[3]:=a[4]; a[4]:=temp;
end;
if a[2]>a[3] then begin
temp:=a[2]; a[2]:=a[3]; a[3]:=temp;
end;
if a[1]>a[2] then begin
temp:=a[1]; a[1]:=a[2]; a[2]:=temp;
end;
Попробуем записать в цикле:
for i:=1 to k do
if a[i]>a[i+1] then begin
temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
end;Как здесь меняется k? Сначала мы проверяли условие один раз (k=1), затем 2 раза (k=2), и т.д. так дошли до проверки условий 4 раза (k=4).
for k:=1 to 4 do
for i:=1 to k do
if a[i]>a[i+1] then begin
temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
end;Если  число элементов принять за переменную n, то конечное значение параметра k ожно записать в виде n-1.
for k:=1 to n-1 do
for i:=1 to k do
if a[i]>a[i+1] then begin
temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
end; Но здесь мы не учли, что проверять условие нужно не до первого элемента, а достаточно до первого невыполненного условия. Можно для остановки цикла добавить веточку else, в которой останавливаем внутренний цикл:
for k:=1 to n-1 do
for i:=1 to k do
if a[i]>a[i+1] then begin
temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
end 
else 
break;
Иногда внутренний цикл записывают с помощью цикла While:
for k:=1 to n-1 do
begin
i:=k;
while a[i]>a[i+1] do begin
temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
 i:=i-1;
end;
end;
Но в этом алгоритме легко выйти за пределеы массива, когда индекс станет равен 0. В этом случае можно ввести еще один нулевой элемент массива и задать его равным a[i+1].

for k:=1 to n-1 do
begin
i:=k;a[0]:=a[k+1];

while a[i]>a[i+1] do begin
temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
 i:=i-1;
end;
end;

Или проверять на граничное условие в самом цикле, причем ставить его нужно первым (при этом компилятору нужно отметить опцию, которая отвечает за оптимизацию логических выражений, т.е. если первое условие в логическом умножении (and) будет ложно, то остальные проверяться не будут, все равно все выражение будет ложно; и наоборот, если в логическом сложении (or) первое выражение будет истинным, то всё выражение будет истинным, поэтому остальные не проверяются):

for k:=1 to n-1 do
begin
i:=k;
while ( i>0) and (a[i]>a[i+1]) do begin
temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
 i:=i-1;
end;
end;

В некоторых алгоритмах сортировки вставками упрощают перестановку: запоминают a[k+1] в переменную temp, в цикле while сравнивают уже с temp и переприсваивают на предыдущий a[i+1]:=a[i], а затем после цикла ставят temp на "свое место":
for k:=1 to n-1 do
begin
i:=k;
temp:=a[i+1];
while ( i>0) and (a[i]>temp) do begin
 a[i+1]:=a[i];
 i:=i-1;
end;
a[i+1]:=temp;
end;
Но цикл While по сравнению с циклом For работает чуть медленнее и это нужно учитывать, если в программе важна скорость.

Для рабты не всегда нужно знать все алгоритмы сортировки, но, как в математике, если знаешь как вывести формулу, всегда её выведешь. Так и в программировании, если знаешь как работает алгоритм, всегда напишешь его код.

Я не разобрала еще челночную сортировку. Её принцип похож на работу челнока в ткацком станке (на челнок  наматывают нить, которая проходит между двух пересекающихся нитей туда и обратно). Этот алгоритм похож на сортировку пузырька, который повторяется в прямом и обратном направлении, но каждый раз границы его прохода сужаются и для числа элементов n потребуется выполнить внешний цикл (n div 2) раз. Попробуйте самостоятельно придти вот к такому алгоритму:
for k:=1 to n div 2 do begin
for i:=k to n-k do
if a[i]>a[i+1] then
begin
temp:=a[i];
a[i]:=a[i+1];
a[i+1]:= temp;
end;
for i:=n-k downto k+1 do
if a[i]<a[i-1] then
begin
temp:=a[i];
a[i]:=a[i-1];
a[i-1]:= temp;
end;
end;
end;


Все эти алгоритмы не являются быстрыми. Про быстрые алгоритмы, такие как алгоритм Хоара, Шелла и другие, можно найти на сайте algolist.manual.ru и на других сайтах. Вот еще примеры алгоритмов сортировки:
 1)
 for k:=1 to n-1 do
 for i:=1 to n-1 do
   if a[i]<a[i+1] then begin
   temp:=a[i]; a[i]:=a[i+1]; a[i+1]:=temp;
 end; 

 2)
 for k:=1 to n-1 do
 for i:=k+1 to n do
   if a[k]<a[i] then begin
   temp:=a[k]; a[k]:=a[i]; a[i]:=temp;
 end;

Попробуйте разобрать на примере и сравнить с известными сортировками.
 
 

Комментариев нет:

Отправить комментарий