Алгоритм 3. Сортировка Шейкером в Delphi.

   Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N — количество элементов. Реализация данного алгоритма выглядит так: Program ShakerSort; Var A : array[1..1000] of integer; N,i,j,p : integer; Min, Max : integer; Begin {Определение размера массива A — N) и его заполнение} … {сортировка данных} for i:=1 to n div 2 do begin if A[i]>A[i+1] then begin Min:=i+1; Max:=i; end else begin Min:=i; Max:=i+1; end; for j:=i+2 to n-i+1 do if A[j]>A[Max] then Max:=j else if A[j]<A[Min] then Min:=j; {Обмен элементов} P:=A[i]; A[i]:=A[min]; A[min]:=P; if max=i then max:=min; P:=A[N-i+1]; A[N-i+1]:=A[max]; A[max]:=P; end; {Вывод отсортированного массива A} … End.    Рассмотрев эти методы, сделаем определенные выводы. Их объединяет не только то, что они сортируют данные, но также и время их работы. В каждом из алгоритмов присутствуют вложенные циклы, время выполнения которых зависит от размера входных данных. Значит, общее время выполнения программ есть O(n2) (константа, умноженная на n2). Следует отметить, что первые два алгоритма используют также O(n2) перестановок, в то время как третий использует их O(n). Отсюда следует, что метод Шейкера является более выгодным для сортировки данных на внешних носителях информации.    Если вы думаете, что бравые «алгоритмщики» остановились на достигнутом, то вы ошибаетесь. Видите ли, временная оценка O(n2) показалась им слишком громоздкой, и они, жадины такие, решили еще потратить свое время, чтобы впоследствии сэкономить наше. Итак, давайте теперь рассмотрим более быстрые алгоритмы.

Алгоритм 4. Сортировка слиянием в Delphi.

   Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную. Корректность данного метода практически очевидна, поэтому перейдем к реализации. Program SlivSort; Var A,B : array[1..1000] of integer; N : integer; Procedure Sliv(p,q : integer); {процедура сливающая массивы} Var r,i,j,k : integer; Begin r:=(p+q) div 2; i:=p; j:=r+1; for k:=p to q do if (i<=r) and ((j>q) or (a[i]<a[j])) then begin b[k]:=a[i]; i:=i+1; end else begin b[k]:=a[j]; j:=j+1; end ; for k:=p to q do a[k]:=b[k]; End; Procedure Sort(p,q : integer); {p,q — индексы начала и конца сортируемой части массива} Begin if p<q then {массив из одного элемента тривиально упорядочен} begin Sort(p,(p+q) div 2); Sort((p+q) div 2 + 1,q); Sliv(p,q); end; End; Begin {Определение размера массива A — N) и его заполнение} … {запуск сортирующей процедуры} Sort(1,N); {Вывод отсортированного массива A} … End.    Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай T(n) — время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n)=2T(n/2)+O(n) (O(n) — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение: T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n/2)+O(n)=4T(n/4)+2O(n)= … = 2kT(1)+kO(n)    Осталось оценить k. Мы знаем, что 2k=n, а значит k=log2n. Уравнение примет вид T(n)=nT(1)+ log2nO(n). Так как T(1) — константа, то T(n)=O(n)+log2nO(n)=O(nlog2n). То есть, оценка времени работы сортировки слиянием меньше, чем у первых трех алгоритмов (я прошу прощения у тех, кто не понял мои рассуждения или не согласен с ними, — просто поверьте мне на слово). Перед тем как объяснить, чем этот метод лучше, рассмотрим еще один алгоритм.