Сочинения

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

Пусть в массиве А з элемента A [L ] начинается упорядоченный участок длиной m-L + 1, а из элемента А [га+1] — участок длиной R-m. Под упорядоченным участком (отрезком или серией) понимаем участок, который не является частью другого упорядоченного участка. Например, длина таких упорядоченных участков равняется m-L + 1 = 3 и R-m = 3.

• из
• L         m         m+1     R
• Они объединяются в такой участок длиной R-L+1 во вспомогательном массиве В.
• 13
• L         m         m+1     R
• Рассмотрим процедуру слияния в массив Z пары сопредельных участков массива X, в котором левая содержит индексы от L до т, а права — відт+1 flo.
• procedure  merge(var   X,Z:aInt;   L,m,R:word); var   k:word;    {индекс   в целевом  массиве} и, j:-word;   {индексы  в половинах) begin
• и:=L;   j:=т+1; for   k: =L   to   R  do
• {заполнение элементов Z[L], …, Z[R]) if и>m then
• begin Z[k]:=X[j]; inc(j) end else if j>r then
• begin Z[k]:=X[i], inc(i) end
• Сортировка линейных массивов
• else   if   X[i]<X[j]    then
• begin   Z[k]:=X[i];   inc(i)    end else  begin   Z[k]:=X[j];   inc(j)   end end;
• Очевидно, тело цикла выполняется R — L + І раз, и каждый раз выполняется 0(1) элементарных действий. Итак, сложность выполнения вызова процедуры merge есть &(R-L + l).

Алгоритм сортировки слиянием заключается в повторении таких шагов слияния пар. В массиве происходит поиск пары сопредельных упорядоченных участков, которые объединяются в один участок вспомогательного массива, например, с помощью процедуры merge. Потом происходит поиск и объединяется следующая пара и т.п.. Возможно, в конце останется участок, который не имеет пары, — ее будет скопировано без перемен. На следующем шаге происходит подобное слияние пар участков вспомогательного массива в основной. Шаги повторяются, пока какой-либо из массивов не превратится на один упорядоченный участок. Если это вспомогательный массив, он копируется в основной. Продемонстрируем выполнение алгоритма на массиве А = < 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> длиной п = 11.

Упорядоченные последовательности выделены дужками < >, пары участков, которые объединяются, отделенные «;», В— имя вспомогательного массива.

• А = «11Х10>; <9><8>; <7><6>; <5><4>; <3><2>; <1»
• В= «10, 11X8, 9>; <6, 7X4, 5>; <2, 3><1»
• Л = «8, 9, 10, 11X4, 5, 6, 7>;<1,2, С»
• Я = «4, 5,6, 7, 8, 9, 10, 11X1,2,3»
• Л = <1,2, 3, 4, 5,6, 7, 8, 9, 10, 11>

Как видим, массив отсортирован за четыре шага слияния.

После первого шага слияния длина упорядоченных участков не меньше 2 (за исключением, возможно, «хвоста» длиной 1), после второго — не меньше 4 (кроме, возможно, «хвоста» меньшей длины) и т.п.. Итак, после /-го шага длина упорядоченных участков, кроме, возможно, «хвоста», не меньше 2′. Пусть п — количество элементов массива. На последнему, к-му, шаге объединяются две участка; первая из них имеет длину не меньше 24″1, причем 2*»1 < г.  Итак, количество шагов к < log« + l. За счет возможного дополнительного копирования количество шагов надо увеличить на 1, но оценка 0(logn) сохранится. На каждом шаге общее количество элементарных действий есть 0(и), поэтому сложность алгоритма — 0(и • log п).

Реализуем алгоритм сортировки слиянием с помощью процедуры sortByMrg. Шаг слияния участков одного массива в другого оформим функцией mergeStep. Она возвращает признак того, что на шаге слияния было найдено хотя бы одну пару упорядоченных участков. Если пара не найдено, то массив, начальный в вызове функции, отсортировано. На непарных шагах слияния функция mergeStep выполняет слияние участков основного массива А у вспомогательный массив В, на парных — наоборот. Якшо массив, начальный в вызове mergeStep, оказался отсортированным на парном шаге слияния, значит, это массив В, и его надо скопировать в основной массив А, А если на непарном шаге, то это массив А, и больше ничего делать не надо.

Пара сопредельных упорядоченных участков и-елементного массива (первый из них начинается индексом left) ищет функция findPair. Она возвращает признак того, что пар найден. Правые границы участков сохраняются в ее параметрах mid и right. Если после ее вызова исполняется условие (lef t=l) and (right=n), то пара не найдено, т.е. массив отсортирован. Для слияния используем процедуру merge (см. выше). Вспомогательная процедура копирования участка массива в другой массив copy Аг есть очевидной.

• procedure copyAr<var X,r:alnt;
• left,right:word)); var и:word; begin
• for i:= left to right do Y[i]:= X[i] end; function findPair(var X:alnt; n,left:word;
• var mid, right   word): boolean; {функция возвращает признак «того, что пара сопредельных упорядоченные участки найдены} begin
• findPair := false; if left <= n then
• Сортировка линейных массивов
• begin
• mid := left;
• while (mid<n)and(X[mid]<=X[mid+1]) do
• inc(mid); {(mid=n) or (X[mid]>X[mid+l])} if mid~n    {правая граница — конец массива} then right:=mid else
• begin {поиск правой границы} findPair := true; right := mid+1; while(right<n)and(X[right]<=X [right+1])
• do inc(right); {(right=n) or (X[right]>X[right+l]} end; end; end;
• function mergeStep(var X,Y:aInt; n.word): boolean;
• {функция возвращает признак того, что слияние массива X в массив Y состоялось} var left,mid,right:word; begin
• mergestep:=true; left:=l;
• while findPair(X,n,left,mid,right) do begin merge(X,Y,left,mid,right) ; left:=right+l end;
• {последний вызов findPair возвратил false} if (left=l)and(right=n)
• then mergeStep:=false {массив X отсортировано} else if left<=n
• then copyAr(X,Y,left,n); {копирование «хвоста»} end;
• procedure sortByMrg(var A:alnt; n:word); var B:alnt;    {вспомогательный массив}

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

Сочинение! Обязательно сохрани - » Сортировка «слиянием» . Потом не будешь искать!

Запись была опубликована 09.10.2009 в 15:36 в категории Изучаем информатику. Вы можете следить за ответами в этой записи через RSS 2.0 ленты.