3. Лабораторная работа «Сравнение двух типов сортировок». Постановка задачи сортировки

Упорядочить массив a[1..n] по неубыванию в соответствии с линейным порядком (), заданным на элементах данного массива, путём перестановки его элементов. (Отношение строгого порядка (<) определим следующим образом: b<c, если bc и b ≠ c)

Сортировка с помощью d-кучи

Реализация алгоритма сортировки с помощью d-кучи (см. [1], [2]) массива a длины n осуществляется процедурой SORT_D(a, n). При этом после выполнения последней итерации цикла while массив a упорядочен по невозрастанию, а после исполнения цикла for упорядочивается по неубыванию.

В данной задаче массивом ключей d-кучи является массив a.

procedure SORT_D(var a, n, d);

begin

ОБРАЗОВАTЬ_ОЧЕРЕДЬ(a,n,d);

nq:= n; while nq>1 do ИЗЪЯТИЕ_МИНИМУМА (a1, a, n, d);

for i := 1 to (n mod 2) do a[i]a[n-i+1];

end;

Временная сложность сортировки с помощью d–кучи (d  константа, не меньше 2) оценивается сверху величиной O(nlog n).

Пузырьковая сортировка

Пузырьковая сортировка (см. [2]) относится к типу «бесхитростных» и заключается в выполнении следующих операций:

procedure BUBBLE_SORT(var a, n) begin for i=1 to n-1 do for j=i+1 to n-1 do if (a[j]<a[i]) then swap(i,j); end;

Процедура swap(i,j) состоит в перемене местами элементов a[i] и a[j]. Временная сложность пузырьковой сортировки оценивается сверху величиной О(n²).

Быстрая сортировка

Быстрая сортировка (см. [1]) относится к типу алгоритмов «разделяй и властвуй». Для того чтобы отсортировать по неубыванию массив a[1..n], надо выполнить процедуру SORT_QUICK(a, 1, n). Операция РАЗДЕЛЯЙ(a, i, j, i1) путем перестановки элементов массива a изменяет его так, чтобы

a[i], …, a[i1-1] ≤ a[i1] ≤ a[i1+1], …, a[j], одновременно определяя число i1.

procedure SORT_QUICK (var a, i, j);

begin

if i < j then begin

РАЗДЕЛЯЙ (a, i, j, i1);

SORT_QUICK (a, i, i1-1); SORT_QUICK (a, i1+1, j);

end;

end;

procedure РАЗДЕЛЯЙ (var a, i, j, var i1);

begin

k:= (i+j)mod(2); b:= a[k];

i1:= i; j1:= j;

repeat

while a[j1] < b & j1 > i do j1:= j1-1;

while a[i1] > b & i1 <j do i1:= i1+1;

if i1 <= j1 then begin

a[i1]a[j1]; i1:= i1+1; j1:= j1-1;

end;

until i1 > j1;

end;

Временная сложность быстрой сортировки n элементного массива оценивается сверху величиной O(n²), однако, в среднем быстрая сортировка выполняется за время O(nlog (n)).

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

Сортировка слиянием (см. [2]) относится к типу алгоритмов “объединяй и властвуй”.

Предположим, что у нас есть процедура СЛИВАЙ(i,j,k), которая два уже отсортированных сегмента a[i…j-1] и a[j…k] преобразует (сливает) в один сегмент a[i…k], делая его полностью отсортированным. Тогда рекурсивная процедура

procedure CОРТИРУЙ(i,j); begin if(i=j) then exit(); else {m=(i+j) div 2; CОРТИРУЙ(i,m); СОРТИРУЙ(m+1,j);СЛИВАЙ(i,m,j);} end;

выполняет сортировку всего сегмента a[i…k], а для сортировки всего исходного массива необходимо выполнить вызов СОРТИРУЙ(1,n). Временная сложность сортировки слиянием есть О(nlog(n)).