Простейшие методы сортировки

Существует довольно много различных методов сортировки, отличающихся друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки, время выполнения и объем занимаемой ОП. Рассмотрим подробно некоторые из указанных методов.

Сначала рассмотрим два метода сортировки: сортировку выбором (линейную) и сортировку обменом (пузырьковую).

Оба метода не очень эффективны и на практике используются крайне редко. Но тогда почему ими нужно вообще заниматься?

Во-первых, во многих простых случаях (например, когда требуется отсортировать всего 20-25 чисел) они вполне удовлетворительны.

Во-вторых, эти методы интересны для нас тем, что в них моделируется естественное поведение человека, осуществляющего сортировку в ручную.

Именно эти два метода легче всего описываются в форме четких алгоритмов и приводят к простой программной реализации.

 

 

Алгоритм линейной сортировки (метод прямого выбора)

Сортировка выбором состоит в том, что сначала в неупорядоченной последовательности выбирается минимальный (максимальный) элемент последовательности.

Затем этот элемент исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную, и процесс повторяется до тех пор, пока все элементы не будут выбраны.

Очевидно, что выбранные элементы образуют упорядоченную последовательность.

Выбранный в исходной последовательности минимальный элемент размещается на предназначенное ему место упорядоченной последовательности несколькими способами:

1. Минимальный элемент после i-го просмотра перемещается на i-е место (i=1, 2, 3,...) другого массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое (малое) число, превосходящее (меньшее) по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр. Очевидно, что при этом размер обрабатываемого массива на 1 меньше размера предыдущего.

2. Минимальный элемент после i-го просмотра перемещается на i-ое место (i=1, 2, 3,...) заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого массива на 1 меньше размера предыдущего.

Этот метод сортировки обычно применяется для массивов, не содержащих повторяющихся элементов.

Для достижения поставленной цели можно действовать следующим образом:

1) выбрать максимальный элемент массива;

2) поменять его местами с последним элементом (после этого наибольший элемент будет стоять на своем месте);

3) повторить пункты 1-2 с оставшимися N-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним; (N-1)-м элементом массива и так далее, пока не останется один элемент, уже стоящий на своем месте.

Всего потребуется N-1 раз выполнить эту последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а не отсортированная, соответственно, уменьшаться.

Итак, этот метод основывается на нахождении максимального (минимального) значения и перестановках. Удачнее всего организовать эти действия в виде вспомогательных алгоритмов (процедур и функций).

Приведем процедуры, соответствующие обоим способам.

Посмотрим выполнение этого алгоритма на примере следующей последовательности:

Способ                                       2 способ

4   5    2  1   3                 4  5    2   1   3       

4   3   2  1   5                  4   -1  2   1   3                               5

1   3   2 4   5                  -1 -1  2   1   3                       4   5

1   2   3 4   5                  -1 -1  2    1   -1          3   4   5

1   2    3  4 5                  -1 -1  -1 1    -1           2   3   4   5

                                                        -1 -1  -1 -1 -1 1  2   3   4   5

Задание:

1. Подсчитайте количество произведенных сравнений (a_i<a_j).

2. Подсчитать количество произведенных перестановок.

 

В процедуре сортировки выбором в первом способе будем использовать две вспомогательные функции: 1) IndMin, определяющую индекс минимального элемента массива a; 2) Max, возвращающую значение максимального элемента массива a.

 

procedure Choice_Sort1(a: arrtype; var b: arrtype);

var maximum, i, j: integer; { maximum - максимальный

 begin                     элемент сортируемого массива }

maximum:= Max (a); { Определяем максимальный элемент массива }

for i:= 1 to n do { n раз выполняем следующие действия }

   begin

      {в i-ю ячейку массива b записываем минимальный элемент массива a}

       j:= IndMin(a); b[ i ]:= a[ i ];

       { а на месте последнего размещаем число,

          превосходящее любой элемент исходного массива }

       a[ j ]:= maximum + 1

   end

end;

              

где функции IndMin и Max имеют вид:

{ Функция, определяющая индекс минимального элемента массива a }

function IndMin (a: arrtype): integer;

var i, imin: integer; { imin- текущее значение искомой величины}

begin

imin:= 1;

for i:= 2 to n do

   if a[ i ] < a[ imin ] then imin:= i;

IndMin:= imin

end;

 

{ Функция, возвращающая значение максимального элемента массива a }

function Max(a: arrtype): integer;

var i, m: integer; { m - текущее значение искомой величины }

begin

m:= a[ 1 ];

for i:= 2 to n do

   if a[ i ] > m then m:= a[ i ];

Max:= m

end;

 

Так как приведенные процедуры используют для сортировки дополнительный массив, то в основной программе при выводе на экран упорядоченной последовательности, как и в разделе 1, следует использовать массив b.

 

В программах, относящихся к сортировке вторым способом, будем использовать вспомогательную функцию IndMin, определяющую индекс минимального элемента из списка переменной длины, начиная от элемента с некоторым индексом start и до последнего элемента массива a.

Функция, определяющая индекс минимального элемента массива a среди элементов, начиная с элемента с индексом start:

 

function IndMin(a: arrtype; start: integer): integer;

var i, imin: integer; {imin - текущее значение искомой величины}

begin

imin:= start;

for i:= start + 1 to n do

   if a[ i ] < a[ imin ] then imin:= i;

IndMin:= imin

end;

 

Процедура, обеспечивающая обмен значениями двух величин:

procedure Swap(var a, b: integer);

var c: integer;

begin

c:= a; a:= b; b:= c

end;

 

Процедура сортировки массива a:

procedure Choice_Sort2(var a: integer)

var i: integer

begin

for i:= 1 to n-1 do

   Swap(a[ IndMin(a, i) ], a[ i ])

end;

Характеристики алгоритма следующие: число сравнений равно С= (n²-n)/2. Минимальное количество пересылок (присваиваний) для массива отсортированного равно M_min=3(n-1).

Для массива, отсортированного в обратном порядке, значение максимальное равно M_max=n²/4 +3(n-1).

Среднее значение можно вычислить для всех n перестановок ключей, число которых равно n!, Mср=nln(n²)+0.57, где 0.57- Эйлерова константа.

 

 

Алгоритм сортировки обменом (метод  "Пузырька")

Сортировка обменом - метод, при котором все соседние элементы массива попарно сравниваются друг с другом и меняются местами в том случае, если предшествующий элемент больше последующего. В результате этого максимальный элемент постепенно смещается вправо и, в конце концов, занимает свое крайне правое место в массиве, после чего он исключается из дальнейшей обработки. Затем процесс повторяется, и свое место занимает второй по величине элемент, который также исключается из дальнейшего рассмотрения. Так продолжается до тех пор, пока вся последовательность не будет упорядочена.

Если последовательность сортируемых чисел расположить вертикально (первый элемент - внизу) и проследить за перемещениями элементов (см рис.), то можно увидеть, что большие элементы, подобно пузырькам воздуха в воде, "всплывают" на соответствующую позицию.

Поэтому сортировку, таким образом называют еще сортировкой методом "пузырька", или "пузырьковой" сортировкой.

Сортировка методом простого обмена может быть применена для любого массива.

Итак, в сортировке "обменом" все соседние элементы попарно сравниваются друг с другом и меняются местами, если предшествующий элемент больше последующего. То есть мы опять основываемся на уже отработанных алгоритмах перестановки элементов.

 

Например, требуется провести сортировку массива:

30, 17, 73, 47, 22, 11, 65, 54

            54     73   73   73   73   73

            65     54   65   65   65   65

            11     65   54   54   54   54

            22     11   47   47   47   47

            47     22   11   30   30   30

            73     47   22   11   22   22

            17     30   30   22   11   17

            30     17   17   17   17   11

Проход   1        2         3         4         5

 

Рис. 2. «Пузырьковая» сортировка массива

 

Ниже представлены процедуры сортировки массива методом «пузырька». В них использованы величины:

r - правая граница (индекс элемента) участка массива, обрабатываемого на каждом проходе;

i - индекс «левого» элемента из пары сравниваемых элементов (a[i] и a[i+1]).

 

procedure Bubble_Sort(var a: arrtype);

var r, i: integer;

begin

for r:= n downto 2 do

   for i:= 1 to r - 1 do

       if a[i] > a[i+1] then Swap(a[i], a[i+1])

end;

 

где процедура Swap выполняет обмен значениями двух элементов массива.

 

4 5 2 1 3               1 проход

4 5 2 1 3

4 2 5 1 3

4 2 1 5 3

4 2 1 3 5

4 2 1 3 5                2 проход

2 4 1 3 5

2 1 4 3 5

2 1 3 4 5

2 1 3  4 5                3 проход

1 2 3  4 5

1 2 3 4 5

1 2 3 4 5                4 проход

1 2 3 4 5

 

Число сравнений C в методе пузырька равно С= (n²-n)/2.

Минимальное количество пересылок (присваиваний) для массива отсортированного равно Mmin=0.

Для массива, отсортированного в обратном порядке, значение максимальное равно Mmax=3/2*(n²-n).

Среднее значение можно вычислить для всех n перестановок ключей, число которых равно n!, Mср=3/4*(n²-n).

В заключение заметим, что метод пузырька не обладает никакими достоинствами, кроме легко запоминающегося названия.

 

 

Усовершенствованная "пузырьковая" сортировка

Нетрудно заметить, что в приведенных процедурах сравнения элементов будут продолжаться даже после того, как массив станет упорядоченным после некоторого, не последнего, прохода. В зависимости от начальных данных массив может быть уже отсортирован уже на K-ом прохождении.

Но сравнения элементов (бесполезные) продолжаются. Ясно, что если на очередном проходе не было сделано ни одного обмена, то массив стал упорядоченным и сортировку можно прекратить.

Если мы будем фиксировать этот факт, то несущественное усложнение приведенной процедуры может дать существенный выигрыш во времени выполнения программы. Для этого можно использовать некоторую величину логического типа was _ swap, определяющую, был ли обмен при последнем проходе, и очередной проход проводить только в случае, если обмен был. Приведем процедуры, учитывающие это обстоятельство.

 

procedure Bubble_Sort(var a: arrtype);

var r, i: integer;

was_swap: Boolean; {был обмен: was_swap = true,

                    не было: was_swap = false }

begin

was_swap:= true;

r:= n;

while (r >= 2) and was_swap do

   begin

       was_swap:= false;

       for i:= 1 to r - 1 do

           if a[ i ] > a[ i + 1 ] then

           begin

               Swap(a[ i ], a[ i + 1 ]);

               was_swap:= true;

           end;

       r:= r - 1

   end

end;

 

Процесс совершенствования метода «пузырька» можно продолжить, если фиксировать не только сам факт обмена, но и место (индекс) последнего обмена, а затем учитывать его для уточнения правой границы r обрабатываемого участка массива.

 

Соответствующая процедура имеет вид:

 

procedure Bubble_Sort(var a: arrtype);

var r, i: integer;

was_swap: Boolean; {был обмен: was_swap = true,

                    не было: was_swap = false }

begin

was_swap:= true;

r:= n;

while (r >= 2) and was_swap do

   begin

       was_swap:= false;

       for i:= 1 to r - 1 do

           if a[ i ] > a[ i + 1 ] then

           begin

               Swap(a[ i ], a[ i + 1 ]);

               was_swap:= true;

               {«Свое» место занял элемент с индексом i+1}

           end;

             r:= i {Новая правая граница

                     обрабатываемого участка массива}

   end

end;

 

 

"Шейкер" - сортировка

Несмотря на все сделанные выше усовершенствования, «пузырьковая» сортировка следующего (почти упорядоченного!) массива 5, 7, 12, 28, 36, 85, 2 будет проведена за семь проходов.

Это связано с тем, что при сортировке рассматриваемым методом за один проход элемент не может переместиться влево больше чем на одну позицию. Так что если минимальный элемент массива находится в его правом конце (как в рассматриваемом примере), то придется выполнить максимальное число проходов.

Поэтому естественно напрашивается еще одно улучшение метода «пузырьковой» сортировки — запоминать не только факт обмена, но и место последнего обмена, так как ясно, что после него все пары расположены уже в правильном порядке. В этом случае время сортировки может несколько сократиться.

Еще одно улучшение мы добавим, периодически меняя направление сортировки, которое борется с некоторой асимметрией пузырькового метода. Асимметрия заключается в том, «тяжелый» элемент в «легком» конце массива более быстро всплывает на свое место, чем «легкий» элемент в «тяжелом» конце.

Действительно, массив 5 1 2 3 4 можно отсортировать за одни проход, а массив 2 3 4 5 1 будет отсортирован только на последнем 5 проходе. Поэтому массив 5 1 2 3 4 разумно сортировать слева направо, а массив 2 3 4 5 1 – справа налево.

 

Такой метод сортировки называется "шейкер"-сортировкой (от английского слова shake- трясти, встряхивать).

Его работа показана на рис. 3 на примере сортировки массива из 8 элементов:

67, 6, 18, 94, 42, 12, 55, 4

                                  4   94   94   94   94

                                55   4   55   67   67

                                12   55   12   55   55

                                42   12   42   12   42

                                94   42   67   42   18

                                18   67   18   18   12

                                  6   18   6   6     6

                                67   6   4   4   4

Направление прохода

                                                              Рис. 3

 

В процедуре, использующей «шейкер»-сортировку, будем использовать две новые величины:

l - левую границу (индекс) участка массива, обрабатываемого на каждом проходе;

r - то же, правую, а процесс упорядочения массива будем проводить, пока соблюдается условие l < r.

 

На школьном алгоритмическом языке  такая процедура может быть представлена следующим образом:

алг Shaker_Sort(арг рез цел таб a[ 1: n ])

нач цел l, r, i, лог was_swap

was_swap:= да

l:= 1; r: = n

нц пока l < r и was_swap

   was_swap:= нет

   нц для i от l до r -1   | Проход «слева направо»

       если a[ i ] > a[ i + 1 ]

           то Swap(a[ i ], a[ i + 1 ])

                 was_swap:= да

       все

   кц

   r:= r - 1

  нц для i от r до l + 1 шаг -1 | Проход «справа налево»

       если a[ i ] < a[ i - 1 ]

           то Swap(a[ i ], a[ i - 1 ])

                 was_swap:= да

       все

   кц

   l:= l + 1

кц

кон

 

Как и в случае метода «пузырька», шейкер-сортировку можно ускорить, если фиксировать места (индексы) последнего обмена при проходах слева направо и справа налево, а затем использовать их для уточнения границ обрабатываемого участка массива. Ниже приведены соответствующие процедуры.

 

procedure Shaker_Sort(var a: arrtype);

var l, r, i: integer; was_swap: boolean;  

begin

was_swap:= true;

l:= 1; r:= n;

while (l < r) and was_swap do      

   begin

       was_swap:= false;

       for i:= 1 to r - 1 do           { Проход «слева направо» }

           if a[ i ] > a[ i + 1 ] then

           begin

               Swap(a[ i ], a[ i + 1 ]);

               was_swap:= true;

               { «Свое» место занял элемент с индексом i + 1 }

                r:= i { Новая правая граница обрабатываемого участка массива }

           end;

       for i:= 1 to r - 1 do           { Проход «справа налево» } проверить for i:=r downto l+1

           if a[ i ] < a[ i - 1 ] then

           begin

               Swap(a[ i ], a[ i - 1 ]);

               was_swap:= true;

               { «Свое» место занял элемент с индексом i - 1 }

                l:= i { Новая левая граница обрабатываемого участка массива }

           end;

    end

end;

 

 

Procedure Shakesort(var x: vector);

var i,j,r, l, buf:integer;

begin

l:=2; r:=n; i:=n;

repeat

for j:=r downto l do

if x[j-1]>x[j] then

   begin

           buf:=x[j-1]; x[j-1]:=x[j]; x[j]:=buf;

       i:=j

    end;

l:=i+1;

for j:= l to r do

if x[j-1]>x[j] then

   begin

        buf:=x[j-1]; x[j-1]:=x[j]; x[j]:=buf; i:=j

    end;

r:=i-1;

until l>r

end; {shakesort}

 

Заметим, что предложенное усовершенствование никак не влияет на количество обменов, оно лишь уменьшает число сравнений ключей. К сожалению, обмен двух элементов – намного более дорогостоящая операция, чем сравнения ключей, поэтому усовершенствования дают на практике значительно меньший эффект, чем следовало ожидать.

Алгоритм шейкер-сортировки выгодно использовать в том случае, когда известно, что элементы уже почти упорядочены, то есть ожидается малое число перестановок.

 

 

Сортировка подсчетом

Этот простой и легкий для понимания метод заключается в том, что каждый элемент массива сравнивается со всеми остальными. Место каждого элемента в отсортированном массиве зависит от числа элементов, меньших его.

Иными словами, если некоторый элемент превышает 13 других, то его место в упорядоченной последовательности — 14. Следовательно, для сортировки необходимо сравнить попарно все элементы и подсчитать, сколько из них меньше каждого отдельного элемента.

После этого все элементы исходного массива можно разместить на соответствующих им местах в новом, специально созданном массиве.

Используются следующие величины:

i — индекс рассматриваемого элемента;

j — индекс элемента, с которым сравнивается рассматриваемый;

k — число элементов, меньших рассматриваемого.

 

Процедуры, выполняющие сортировку массива a методом подсчета и заполняющая отсортированными элементами массив b:

 

procedure Count_Sort(a:arrtype;var b: arrtype);

var i, j, k: integer;

begin

 for i:=l to n do {Для каждого элемента массива а определяем }

begin           { величину k сравнивая его со всеми }

k:=0;

for j:=1 to i-1 do

  if a[j]<a[i] then k:=k+l;

for j:=i+l to n {остальными элементами) do

  if a[j]<a[i] then k:=k+l;

{ Размещаем элемент a[i] на k+1 месте в массиве b}

b[k+l]:=a[i]

 end;

end;