Обменные сортировки:BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов. Процесс продолжается до тех пор. - презентация

1 Обменные сортировки:BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов. Процесс продолжается до тех пор пока не будут упорядочены все элементы

2 Обменные сортировки:BubbleSort

3

4 for i := n-1 downto 1 do begin Flag := false; for j := 1 to i do if a[j]>a[j+1] then begin Tmp := a[j]; a[j] := a[j+1]; a[j+1] := Tmp; Flag := true; end; if not Flag then Break; end;

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

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

7 Обменные сортировки:ShakerSort procedure ShakerSort; var j, k, L, R:index; x: item; begin L:= 2;R;= n;k:=n; repeat for j:=R downto L do {справа налево} if a[j-1]>a[j] then begin x : = a[j-1]; a[j-1]: = a[j]; a[j]: = x; k:=j end; L:=k+1;

8 Обменные сортировки:ShakerSort for j:=L to R do {слева направо} if a[j-1] >a[j] then begin x := a[j-1]; a[j-1]:= a[j]; a[j] := x; k:=j end; R:=k-1; until L>R; end ShakerSort; shaker

9 Обменные сортировки:ShakerSort число сравнений строго обменном алгоритме: (n 2 -n)/2 Среднее число перемещений: 3 (n 2 -n)/2

10 Обменные сортировки:ShakerSort Минимальное число сравнений Cmin = n1 а среднее число сравнений пропорционально ½(n 2 -n(k2+ln n))

11 Обменные сортировки:QuickSort Выберем наугад какой-либо элемент массива – х Просматриваем массив слева направо, пока не обнаружим элемент Ai>x Просматриваем массив справа налево, пока не встретим Аi

12 Обменные сортировки:QuickSort 1

13 Обменные сортировки:QuickSort

14 Procedure partition; var w,x:item; begin i :=1; j:=n; выбрать X; Repeat while a[i] < x do i:=i+1; while a[j] >x do j:=j-1; if ij end partition;

15 Обменные сортировки:QuickSort Procedure QuickSort; Procedure Sort(L,R:index); var i,j:index; w,x:item; begin i :=L; j:=R; x:= a[(L+R)div2]; Repeat while a[i] < x do i:=i+1; while a[j] >x do j:=j-1; if ij;

16 Обменные сортировки:QuickSort if j>L then Sort (L,j); if i

17 Обменные сортировки:QuickSort Ожидаемое число обменов: (n-1)/6 Общее число сравнений: n*logn Наихудший случай – для сравнения выбирается наибольшее из всех значений в указанной области, те левая часть состоит из n-1, а правая из 1, те производительность ~ n 2

18 Сортировка распределением Пусть каждый элемент массива может принимать M (например, от 0 до M) фиксированных значений. Введем массив Amount[0..M], первоначально обнулив его. Затем для каждого i подсчитаем количество элементов массива A, равных i, и занесем это число в Amount[i]:

19 Сортировка распределением for i := 0 to M do Amount[i] := 0; for i := 1 to N do Inc(Amount[A[i]]);

20 Сортировка распределением Теперь в первые Amount[0] элементов массива A запишем 0, в следующие Amount[1] элементов массива A запишем 1и т.д. до тех пор, пока не дойдем до конца массива A и массива Amount):

21 Сортировка распределением p := 1; for i := 0 to M do for j := 1 to Amount[i] do begin A[p] := i; Inc(p); end;

22 Сортировка распределением Временную сложность метода можно оценить как O(M+N) M появляется в сумме, так как изначально надо обнулить массив Amount, а это требует M действий). Пространственная сложность в этом случае равна O(M), поскольку требуется дополнительная память размером порядка M.

23 Сортировка слиянием Пусть k - положительное целое число. Разобьем массив A[1]..A[n] на отрезки длины k. (Первый - A[1]..A[k], затем A[k+1]..A[2k] и т.д.) Последний отрезок будет неполным, если n не делится нацело на k. Назовем массив k-упорядоченным, если каждый из этих отрезков длины k упорядочен.

24 Сортировка слиянием любой массив 1-упорядочен, так как его подмассивы длиной 1 можно считать упорядоченными. если массив k-упорядочен и n

25 Сортировка слиянием Процедура преобразования k- упорядоченного массива в 2k- упорядоченный: 1. Сгруппировать все подмассивы длины k в пары подмассивов. 2. Пару упорядоченных подмассивов объединить в один упорядоченный подмассив. 3. Проделав это со всеми парами, мы получим 2k-упорядоченный массив:

26 Сортировка слиянием {группировка подмассивов длины 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;

27 Сортировка слиянием Пусть 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);

28 Сортировка слиянием Первое действие может производиться при двух условиях: 1. первый отрезок не кончился (p0 < q); 2. второй отрезок кончился (q0 = r) или не кончился, но элемент в нем не меньше (q0 < r) и (A[p0+1]

29 Сортировка слиянием Окончательный текст 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;

30 Сортировка слиянием while (p0q) or (q0r) do begin if (p0

31 Сортировка слиянием t := r; end {цикла t+k}; k := k *2; A := B End {цикла k}; example

32 Сортировка слиянием Временная сложность O(N*log(N)) (так как преобразование k- упорядоченного массива в 2k- упорядоченный требует порядка N действий и внешний цикл по k совершает порядка log(N) итераций). сравнение