Формулировка задачи сортировки

Сортировки

Сортировки. 1

Введение. 2

Формулировка задачи сортировки. 3

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

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

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

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

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

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

Алгоритм сортировки вставками (метод прямого включения) 2

Размещение путем сравнения и обмена. 4

Размещение путем поиска места и вставки. 5

Более сложные и более эффективные методы сортировки. 3

Алгоритм сортировки Шелла (метод h-сортировки) 2

Обменная сортировка с разделением (сортировка Хоара) 2

Сортировка методом слияний. 5

Простое слияние. 6

Естественное двухпутевое слияние. 8

Рекурсивный алгоритм слияния. 8

Слияние списков. 9

Алгоритм сортировки бинарными вставками. 10

Сортировка с помощью двоичного включения. 11

Топологическая сортировка. 12

Поразрядная сортировка. 16

Пирамидальная сортировка. 19

Рекурсивная сортировка. 22

Сравнительная характеристика методов сортировки. 22

Классификация задач с применением сортировок. 23

1. Задачи заполнения. 23

2. Задачи анализа. 25

3. Задачи поиска. 25

4. Задачи перестановки. 26

Литература. 27

Задачи. 27

 

 

Введение

Изучение методов сортировки — неотъемлемая часть любого курса информатики. Это видно хотя бы по тому факту, что эта тема рассматривается во всех распространенных сегодня учебниках, несмотря на различия в идейных и методических установках их авторов.

Сортировка — это один из наиболее распространенных видов современной обработки данных.

В словарях слово «сортировка» (sorting) определяется как «распределение, отбор по сортам; деление на категории, сорта, разряды», однако, программисты обычно используют это слово в более узком смысле, обозначая им процесс перегруппировки заданного множества объектов в некотором определенном порядке. Этот процесс, пожалуй следовало бы назвать упорядочиванием (ordering) или ранжированием (sequencing). Однако, слово «сортировка» уже прочно вошло в программистский жаргон, поэтому мы будем в дальнейшем использовать слово «сортировка» в узком смысле — «сортировка по порядку».

Считается, что 25% машинного времени систематически тратится на сортировку. Во многих вычислительных системах на нее тратится более половины машинного времени.

Это может означать одно из трех:

1. Либо сортировка имеет много важных применений.

2. Либо ей часто пользуются без нужды.

3. Либо применяются в основном неэффективные алгоритмы.

Любое из предположений содержит долю истины.

 

Еще один немаловажный факт в пользу того, что сортировками надо заниматься – то, что алгоритмы сортировки интересны сами по себе как объект исследования. Методы сортировки позволяют оценивать рабочие характеристики алгоритмов, учат разумно выбирать среди имеющихся методов.

 

Мы встречаемся с отсортированными объектами в телефонных книгах, в оглавлениях книг, в библиотеках, в словарях, на складах - почти везде, где нужно выбирать объекты из предложенного множества.

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

Когда элементы "отсортированы", проще найти, например, телефон товарища в телефонной книге на 500 страниц, быстрее найти слово в словаре на 700 страниц.

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

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

Под сортировкой в курсе ОИВТ обычно понимают процесс размещения элементов заданного множества объектов в некотором определенном порядке, как правило, в порядке возрастания или убывания (когда сортируемыми элементами являются числа) или в алфавитном порядке (при сортировке текстовой информации).

 

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

 

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

Как пишет один из классиков теории программирования Д.Кнут " Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования ".

 

Сортировка производится над некоторым однородным набором данных. В программировании такую структуру для представления однородной информации принято называть массивом.

Основные свойства таких величин:

· массив состоит из множества простых переменных, к которым можно обращаться не по уникальным именам, а по общему имени массива с указанием номера элемента.

· все элементы массива равноправны (однородность массива): имеют одинаковый, содержательный смысл, при обработке над ними совершаются одинаковые операции.

 

Очевидно, что массив может быть результатом алгоритма (заполнение), аргументом (обработка) и аргументом-результатом (модификация).

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

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

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

Реальный интерес представляют задачи перестановки, в которых необходимо переставить элементы заданной таблицы в соответствии с какими-то требованиями. Главная задача перестановки - это сортировка элементов массива, то есть элементы массива необходимо переставить так, чтобы они располагались, например, по возрастанию.

Окончательно получаем такие группы задач:

1. Заполнение

2. Анализ

3. Поиск

4. Перестановка.

 

Фактически все основные приемы построения алгоритмов формируются на линейных массивах. Обработка прямоугольных таблиц приводит к количественному, но не качественному усложнению.

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

 

 

Способ                                       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;

 

 

Примечания

1. Как и в табл. 1, значение, равное 1,0, соответствует минимальному времени сортировки, остальные значения — времени, рассчитанному по отношению к минимальному.

2. В табл. 3 и в других аналогичных таблицах, приведенных ниже, представлены результаты расчетов, полученные без использования в процедурах сортировки вспомогательных процедур (в данном случае Swap, Find_Place и Insert). Такое оформление процедур сортировки приводит к сокращению времени работы программ (хотя вид процедур при этом, естественно, ухудшается).

 

Число сравнений С при вставке в готовую i последовательность составляет самой большое i-1, самое меньшее 1.

Поэтому общее число сравнений: С_min=n-1, C_max==(n²-n)/2-1.

 

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

Procedure InsertBin(var x:vector);

 var j,a,b,s,r, m:integer;

begin

 for j:=2 TO N do

begin

a:= 1; b:= j;

repeat

      s:= (a+b) div 2;

      if x[s]<x[j] then a:=s+1

      else b:=s

until a=b;

r:=x[j];

for m:=j downto a+1 do x[m]:=x[m-1];

x[a]:=r;

end;

 end; {InsertBin}

 

 

Сортировка методом слияний

Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.

Исторически метод слияния является одним из первых методов, предложенных для сортировки на ЭВМ еще в 1954 году, автором его является Джон фон Нейман.

 

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

Пусть массив а [1..n] разбивается на части длиной k, тогда первая часть - a[1], a[2],..., a[k], вторая- a[k+l], a[k+2],..., a[2k] и так далее. Если n не делится на k, то в последней части будет менее k элементов.

После того как массивы-части упорядочены, можно объединить их в упорядоченные массивы-части, состоящие не более чем из 2k элементов, которые далее объединить в упорядоченные массивы длиной не более 4k,и так далее, пока не получится один упорядоченный массив.

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

 

В более узком смысле слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив. Например, слияние двух массивов – 5 8 9 и 1 3 4 10 дает массив 1 3 4 5 8 9 10.

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

Рассмотрим этот метод на примере указанных двух массивов (5, 8, 9) и (1, 3, 4, 5, 8, 9, 10).

 

5     8     9

1     3     4     10

выбираем 1

 

5     8     9

3     4     10

выбираем 3

 

5     8     9

4     10

выбираем 4

 

5     8     9

10

выбираем 5

 

8     9

10

выбираем 8

9

10

выбираем 9

пустой массив

10

выбираем 10

 

Слияние намного более простая процедура, чем сортировка, так как общий объем работы по существу пропорционален количеству элементов m+n, но при этом используется дополнительный массив.

 

Алгоритм двухпутевого слияния реализован в следующей программе для отсортированных массивов x[1..m], y[1..n] с результирующим массивом z[1..n+m]. Небольшое упрощение введено добавлением в конец исходных файлов искусственных стражей x_m+1=y_n+1=¥.

 

Procedure Merge(x:vectorm;y:vectorn; var z: vectornm);

Var i,j,k: integer;

Begin

i:=1; j:=1;

x[m+1]:=Maxint; y[n+1]:=Maxint;

for k:=1 to n+m do

if x[i]<=y[j] then begin z[k]:=x[i]; inc(i) end

else begin z[k]:=y[j]; inc(j) end;

end;

 

 

Простое слияние

Алгоритм слияния, предложенный фон Нейманом, упорядочивает пары соседних чисел. Затем упорядоченные пары сливаются в упорядоченные четверки, восьмерки и т.д. Для хранения упорядоченных серий используется вспомогательный массив Y.

 

X    1     7      3     6      4     2      8     5

Y    1     7     3     6      2     4     5     8

X    1     3     6     7     2     4     5     8

Y    1     2     3     4     5     6     7     8

 

Этот алгоритм называется иногда вверх-направленным слиянием, учитывая направление сливаемых пар.

При слиянии можно выбирать не соседние пары, а элементы, стоящие на концах массива. Алгоритм простого двухпутевого слияния берет элементы с двух концов исходного массива, сливает их в упорядоченные пары и отправляет по очереди в два конца выходного массива.

X    1      7     3     6     4     2     8     5

Y    1     5      2     3      6     4      8     7

X    1     5     7     8      6     4     3     2

Y    1     2     3     4     5     6     7     8

 

Чтобы не запутаться в двух виртуальных массивах, будем использовать один массив двойной длины array[1..2*n]. При этом сначала исходный массив находится в первой половине, в выходной – во второй, а затем наоборот.

Заведем булевскую переменную Up, которая определяет направление слияния: true – из первой половины во вторую, false – из второй половины в первую. Индексы i, j - отвечают за место, из которого берутся элементы для слияния, а k, l – за место куда пересылаются элементы. Переменная P определяет длину сливаемых серий (1, 2, 4, …).

Procedure merge(var x: vector);

Var up: boolean;

i, j, k, l: integer;

P: integer;

Begin

 Up:=true;

 p:=1;

 Repeat

if up then

Begin

 i:=1;j:=n; k:=n+1; l:=2*n;

end

 else

Begin

i:=n+1; j:=2*n; k:=1; l:=n

end;

{слияние p-серии из i, j в к, l}

  Up:=not up;

  P:=2*p

 Until p>=n;

End;

 

Слияние происходит следующим образом: сначала пересылка идет по адресу k, при этом индекс увеличивается на единицу, затем по адресу l, и индекс уменьшается на 1. Для упрощения будем считать, что пересылка всегда идет по адресу k с шагом h, но после каждого слияния будем чередовать h (либо +1, либо -1), а также менять местами значения k и l.

 

h:=1; m:=n;

Repeat

q:=p; r:=p; m:=m-2*p;

{слияние q элементов из i и r элементов из j}

h:=-h;

{обмен k, l};

Until m=0;

Сама процедура слияния должна предусмотреть копирование оставшегося остатка:

 

While (q<>0) and(r<>0) do

if x[i]<x[j]

 then begin x[k]:=x[i]; k:=k+h; i:=i+1; q:=q-1 end

Else begin x[k]:=x[j]; k:=k+h; j:=j-1; r:=r-1 end;

{копирование остатков из i или j}

 

Окончательный текст программы 

Procedure merge(var x: vector);

Var up: boolean;

I, j, k, l, t: integer;

P, h, q, r, m: integer;

Begin

 Up:=true;

 p:=1;

 Repeat

 m:=n; {общее число элементов во

   входных последовательностях,

   которые осталось слить}

 H:=1;

 if up

then

Begin

 i:=1;j:=n; k:=n+1; l:=2*n;

 end

else

Begin

i:=n+1; j:=2*n; k:=1; l:=n

end;

 Repeat

if m>= p then q:=p

      else q:=m; m:=m-q;

if m>= p then r:=p

      else r:=m; m:=m-r;

While (q<>0) and(r<>0) do

if x[i]<x[j]

then

begin

 x[k]:=x[i]; k:=k+h; i:=i+1; q:=q-1

end

else

begin

x[k]:=x[j]; k:=k+h;

 j:=j-1; r:=r-1

end;

 {копирование остатков}

 While r<>0 do

Begin

A[k]:=a[j]; k:=k+h;

 j:=j-1; r:=r-1

  End;

 While q<>0 do

Begin

A[k]:=a[i]; k:=k+h;

i:=i+1; q:=q-1

  End;

H:=-h; T:=k; k:=l; l:=t;

 Until m=0;

 Up:=not up;

 P:=2*p

 Until p>=n;

 if not up then

for i:=1 to n do x[i]:=x[i+n]

End;

Поскольку на каждом проходе p удваивается, то сортировка требует [log₂N] проходов. При каждом проходе перемещаются все N элементов. Поэтому характеристика M для сортировки слиянием оценивается как N*[log₂N].

Число сравнений C меньше, чем М, так как при копировании остатков сравнения не проводятся.

 

 

Слияние списков

Основным недостатком алгоритмов слияния является использование дополнительной памяти размером в N элементов. В действительности, если добавить связи между исходными элементами, то все слияние можно легко произвести, манипулируя связями. Добавление N полей связи, как правило, выгоднее, чем хранение N дополнительных элементов. Кроме того, манипулируя связями, мы отказываемся от «дорогой» операции перемещения записей и экономим время сортировки.

Поэтому рассмотрим алгоритм слияния на связанных списках.

 

Procedure merge (L1, L2: Link; var L: Link);

Var p: link;

Begin

P:=z;

Repeat

if L1^.elem<=L2^.elem

then

   begin

     P^.next:=L1; P:=L1;

     L1:=L1^.next

   end

else

   begin

     P^.next:=L2; P:=L2;

     L2:=L2^.next

   end;

until P^.elem=Maxint;

L:=Z^.next;

z^.next:=z

End;

 

 

В программе списки L1, L2 имеют общий конечный узел («хвост») z, который указывает сам на себя. «Хвост» выполняет несколько полезных функций:

- Z^.elem содержит граничный сторожевой элемент ¥,

- Z^.next при слиянии используется в качестве указателя на начало объединенного списка,

- после слияния Z^.next снова устанавливается на себя.

Сравнение на равенство ключей (<=) делает сортировку устойчивой. Например, списки на рисунке в случае устойчивой сортировки дают в результате 1A, 2B, 2C, 2E, 2F, 3D, 4G.

 

 

1

A

2

B

2

C

3

D

¥

 

 

2

E

2

F

4

G

 

А в случае неустойчивой сортировки

1A, 2E, 2G, 2B, 2C, 3D, 4G.

 

В случае внутреннего слияния связанное распределение памяти имеет явные преимущества перед последовательным распределением: требуется меньше памяти и программа работает на 10-20% быстрее.

 

 

Begin

for i:=2 to n do

    begin x:=a[i]; L:=1; R:=i;

       While L<R do

           begin

              m:=(L+R) div 2; { Находим индекс среднего элемента }

              if a[m]<=x then L:=m+1 else R:=m;

           end;

     { Дальше сдвигаем массив с позиции R +1 до i a [ R +1],…, a [ i ]
      на одну позицию вправо, начиная с места i }

     for j:=i downto (R+1) do a[j]:=a[j-1];

     a[R]:=x;

    end; { Цикла по i }

end; { bin_insert }

Место включения элемента x в последовательность обнаружено когда l=r. Здесь улучшения, порожденные введением двоичного поиска, касаются лишь числа сравнений, а не числа необходимых продвижек (перестановок) чисел.

Поскольку движение элемента занимает значительно больше времени, чем сравнение двух чисел, то фактически улучшения не столь уж существенны, ведь число пересылок (присваиваний) М так и продолжает оставаться порядка n². И на самом деле, сортировка уже отсортированного массива потребует больше времени, чем в случае последовательной сортировки с прямыми включениями. Таким образом, очевидные улучшения часто дают не столь уж большой выигрыш, как это кажется на первый взгляд. Сортировка с помощью включений не кажется столь удобным методом, так как включение одного элемента с последующим сдвигом на одну позицию целой группы элементов не экономно. Лучшие результаты дают методы, где передвижка, пусть на большие расстояния, будет связана лишь с одним единственным элементом. 

 

 

Топологическая сортировка

Топологическая сортировка применяется для элементов, для которых определен частич