САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ1 Обменные сортировки:BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов. Процесс продолжается до тех пор пока не будут упорядочены все элементы

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ2 Обменные сортировки:BubbleSort

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ3 Обменные сортировки:BubbleSort

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ4 Обменные сортировки:BubbleSort:BubbleSort Алгоритм BubbleSort( a, n); for i n-1 downto 1 do Flag false; for j 1 to i do if a[j]>a[j+1] then Tmp a[j]; a[j] a[j+1]; a[j+1] Tmp; Flag true; if not Flag then return a;

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ5 Обменные сортировки:BubbleSort Алгоритм имеет среднюю и максимальную временные сложности O(n 2 ) (два вложенных цикла, зависящих от n линейно). Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к O(n).

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ6 Обменные сортировки:BubbleSort легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются с минимальной скоростью:один шаг за итерацию. массив будет отсортирован за 1 проход, а сортировка последовательности потребует 5 проходов. Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Данный алгоритм иногда называют "шейкер- сортировкой".

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ7 Обменные сортировки:ShakerSort Алгоритм ShakerSort (a,n); L 2; R n; k n; repeat for j R downto L do {справа налево} if a[j-1]>a[j] then x a[j-1]; a[j-1] a[j]; a[j] x; k j L k+1;

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ8 Обменные сортировки:ShakerSort for j L to R do {слева направо} if a[j-1] >a[j] then x a[j-1]; a[j-1] a[j]; a[j] x; k j R k-1; while L< R; shaker

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ9 Обменные сортировки число сравнений строго обменном алгоритме: (n 2 -n)/2 среднее число перемещений: 3 (n 2 -n)/2

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ10 Обменные сортировки минимальное число сравнений Cmin = n1 среднее число сравнений пропорционально ½(n 2 -n(k2+ln n))

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ11 Обменные сортировки:QuickSort Выберем наугад какой-либо элемент массива – х Просматриваем массив слева направо, пока не обнаружим элемент Ai>x Просматриваем массив справа налево, пока не встретим Аi

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ12 Обменные сортировки:QuickSort 1

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ13 Обменные сортировки:QuickSort

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ14 Обменные сортировки:QuickSort Алгоритм partition (a,1,n,x); i 1; j n; выбрать x; repeat while a[i] < x do i i+1; while a[j] >x do j j-1; if i

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ15 Обменные сортировки:QuickSortQuickSort Алгоритм Sort(L,R:index); i L; j R; x a[(L+R) div 2]; partition (a,L,R,x); if j>L then Sort (L,j); if i

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

Дополнения и улучшения алгоритма Первый элемент в сортируемом куске выбирается случайно и запоминается; Участки, меньшие определенного размера, сортируются простыми способами; Иногда исключение рекурсивных вызовов приводит к повышению эффективности.

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ18 Обменные сортировки:QuickSort Ожидаемое число обменов: (n-1)/6 Общее число сравнений: n*logn Наихудший случай – для сравнения выбирается наибольшее из всех значений в указанной области, те левая часть состоит из n-1, а правая из 1, те производительность ~ n 2

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ19 Сортировка распределением Пусть каждый элемент массива может принимать M (например, от 0 до M) фиксированных значений. Введем массив Amount[0..M], первоначально обнулив его. Затем для каждого i подсчитаем количество элементов массива A, равных i, и занесем это число в Amount[i]:

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ20 Сортировка распределением for i := 0 to M do Amount[i] := 0; for i := 1 to N do Inc(Amount[A[i]]);

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ21 Сортировка распределением Теперь в первые Amount[0] элементов массива A запишем 0, в следующие Amount[1] элементов массива A запишем 1и т.д. до тех пор, пока не дойдем до конца массива A и массива Amount):

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ22 Сортировка распределением p := 1; for i := 0 to M do for j := 1 to Amount[i] do begin A[p] := i; Inc(p); end;

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ23 Сортировка распределением Временную сложность метода можно оценить как O(M+N) M появляется в сумме, так как изначально надо обнулить массив Amount, а это требует M действий). Пространственная сложность в этом случае равна O(M), поскольку требуется дополнительная память размером порядка M.

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ24 Сортировка слиянием Divide et impera [дивидэ эт импэра] Парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ25 Сортировка слиянием Разделяй и властвуй 1.Разделение (декомпозиция) задачи на несколько подзадач. 2.Покорение рекурсивное решение этих подзадач. Когда объем подзадачи достаточно мал, выделенные подзадачи решаются непосредственно. 3.Комбинирование решения исходной задачи из решений вспомогательных задач.

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ26 Сортировка слиянием Алгоритм сортировки слиянием (merge sort) Разделение: сортируемая последовательность, состоящая из n элементов, разбивается на две меньшие последовательности, каждая из которых содержит n/2 элементов Покорение: сортировка обеих вспомогательных последовательностей методом слияния Комбинирование: слияние двух отсортированных последовательностей для получения окончательного результата

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ27 Сортировка слиянием Процедура Merge (A,p, q,r), где А массив, а р, q и r индексы, нумерующие элементы массива, такие, что р q < r. В этой процедуре предполагается, что элементы подмассивов A [p..q] и A[q+1..r] упорядочены. Она сливает эти два подмассива в один отсортированный, элементы которого заменяют текущие элементы подмассива А [р..r].

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ28 Сортировка слиянием

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ29 Сортировка слиянием

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ30 Сортировка слиянием

Алгоритм слияния упорядоченных массивов public static int[] merge(int[] a, int[] b) { int na = a.length, nb = b.length, nc; int[] c = new int[nc = na + nb]; int ia = 0, ib = 0, ic = 0; while (ia < na && ib < nb) { if (a[ia] < b[ib]) c[ic++] = a[ia++]; else c[ic++] = b[ib++]; } while (ia < na) c[ic++] = a[ia++]; while (ib < nb) c[ic++] = b[ib++]; return c; }

Сортировка фон Неймана (слиянием) И так далее…

Алгоритм сортировки фон Неймана public static void mergeSort(int[] data) { int n = data.length; // Длина массива int[] altData = new int[n]; // Дополнительный массив int[] from = data, // Указатели "откуда" и "куда" происходит слияние to = altData; int len = 1; // Длина сливаемого фрагмента do { int start = 0; while (start < n) { // Сливаем участки from[start:(start+len-1)] и from[(start+len):(start+2*len-1)] // в to[start:(start+2*len-1)] mergeSection( from, start, Math.min(start+len, n), from, Math.min(start+len, n), Math.min(start+(len

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ34 Сортировка слиянием Пусть k - положительное целое число. Разобьем массив A[1]..A[n] на отрезки длины k. (Первый - A[1]..A[k], затем A[k+1]..A[2k] и т.д.) Последний отрезок будет неполным, если n не делится нацело на k. Назовем массив k-упорядоченным, если каждый из этих отрезков длины k упорядочен.

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ35 Сортировка слиянием любой массив 1-упорядочен, так как его подмассивы длиной 1 можно считать упорядоченными. если массив k-упорядочен и n

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ36 Сортировка слиянием Процедура преобразования k- упорядоченного массива в 2k- упорядоченный: 1. Сгруппировать все подмассивы длины k в пары подмассивов. 2. Пару упорядоченных подмассивов объединить в один упорядоченный подмассив. 3.Проделав это со всеми парами, мы получим 2k-упорядоченный массив:

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ37 Сортировка слиянием {группировка подмассивов длины K в пары} t:=1; while t + k < n do begin p := t; {индекс 1 эл-та 1-ого подмасс.} q := t+k; {индекс 1 эл-та 2-ого подмасс.}... r := min(t+2*k, n);... слияние подмассивов A[p..q-1] и A[q..r-1] t := r; end;

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ38 Сортировка слиянием Пусть p0 и q0 - номера последних элементов участков, подвергшихся слиянию, s0 - последний записанный в массив B элемент. На каждом шаге слияния производится одно из двух действий: 1.B[s0+1]:=A[p0+1]; Inc(p0); Inc(s0); или 2.B[s0+1]:=A[q0+1];{ Inc(q0); Inc(s0);

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ39 Сортировка слиянием Первое действие может производиться при двух условиях: 1. первый отрезок не кончился (p0 < q); 2. второй отрезок кончился (q0 = r) или не кончился, но элемент в нем не меньше (q0 < r) и (A[p0+1]

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ40 Сортировка слиянием Окончательный текст k := 1; while k < N do begin t := 1; while t+k < N do begin p := t; q := t+k; if t+2*k>N then r := N else r := t+2*k; p0 := p; q0 := q; s0 := p;

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ41 Сортировка слиянием while (p0q) or (q0r) do begin if (p0

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ42 Сортировка слиянием t := r; end {цикла t+k}; k := k *2; A := B End {цикла k}; example

САОД, каф.ОСУ, АВТФ, НИУ РФ ТПУ43 Сортировка слиянием Временная сложность O(N*log(N)) (так как преобразование k-упорядоченного массива в 2k-упорядоченный требует порядка N действий и внешний цикл по k совершает порядка log(N) итераций). сравнение