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




НазваниеОбменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов
Дата конвертации23.07.2013
Размер445 b.
ТипПрезентации


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

  • Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов.

  • Процесс продолжается до тех пор пока не будут упорядочены все элементы


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



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



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

  • 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;



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

  • Алгоритм имеет среднюю и максимальную временные сложности O(n2) (два вложенных цикла, зависящих от n линейно).

  • Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к O(n).



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

  • легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются с минимальной скоростью:один шаг за итерацию.

  • массив 2 3 4 5 6 1 будет отсортирован за 1 проход,

  • а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

  • Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов.

  • Данный алгоритм иногда называют "шейкер-сортировкой".



Обменные сортировки: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;



Обменные сортировки: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



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

  • число сравнений строго обменном алгоритме:

  • (n2-n)/2

  • Среднее число перемещений:

  • 3(n2-n)/2



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

  • Минимальное число сравнений

  • Cmin = n—1

  • а среднее число сравнений пропорционально ½(n2-n(k2+ln n))



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

  • Выберем наугад какой-либо элемент массива – х

  • Просматриваем массив слева направо , пока не обнаружим элемент Ai>x

  • Просматриваем массив справа налево, пока не встретим Аi<х

  • Меняем местами эти два элемента

  • Процесс просмотра и обмена продолжается, пока оба просмотра не встретятся



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

  • 1

  • i< k < n: х  ak



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



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

  • 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 i<=j then begin w:=a[i]; a[i]:=a[j];

  • a[j]:=w;Inc(i);Dec(j)

  • end;

  • until i>j

  • end partition;



Обменные сортировки: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 i<=j then begin w:=a[i]; a[i]:=a[j];

  • a[j]:=w;Inc(i);Dec(j)

  • end;

  • until i>j;



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

  • if j>L then Sort (L,j);

  • if ithen Sort (i,R);

  • end Sort;

  • begin

  • Sort (1,n)

  • end QuickSort;



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

  • Ожидаемое число обменов:

  • (n-1)/6

  • Общее число сравнений:

  • n*logn

  • Наихудший случай – для сравнения выбирается наибольшее из всех значений в указанной области, те

  • левая часть состоит из n-1, а правая из 1, те производительность ~ n2



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

  • Пусть каждый элемент массива может принимать M (например, от 0 до M) фиксированных значений.

  • Введем массив Amount[0..M], первоначально обнулив его.

  • Затем для каждого i подсчитаем количество элементов массива A, равных i, и занесем это число в Amount[i]:



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

  • for i := 0 to M do

  • Amount[i] := 0;

  • for i := 1 to N do

  • Inc(Amount[A[i]]);



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

  • Теперь в первые Amount[0] элементов массива A запишем 0,

  • в следующие Amount[1] элементов массива A запишем 1и т.д.

  • до тех пор, пока не дойдем до конца массива A и массива Amount):



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

  • p := 1;

  • for i := 0 to M do

  • for j := 1 to Amount[i] do

  • begin

  • A[p] := i;

  • Inc(p);

  • end;



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

  • Временную сложность метода можно оценить как O(M+N)

  • M появляется в сумме, так как изначально надо обнулить массив Amount, а это требует M действий).

  • Пространственная сложность в этом случае равна O(M), поскольку требуется дополнительная память размером порядка M.



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

  • Пусть k - положительное целое число.

  • Разобьем массив A[1]..A[n] на отрезки длины k.

  • (Первый - A[1]..A[k], затем A[k+1]..A[2k] и т.д.)

  • Последний отрезок будет неполным, если n не делится нацело на k.

  • Назовем массив k-упорядоченным, если каждый из этих отрезков длины k упорядочен.



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

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

  • если массив k-упорядочен и n<=k, то он упорядочен.



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

  • Процедура преобразования k-упорядоченного массива в 2k-упорядоченный:

  • Сгруппировать все подмассивы длины k в пары подмассивов.

  • Пару упорядоченных подмассивов объединить в один упорядоченный подмассив.

  • Проделав это со всеми парами, мы получим 2k-упорядоченный массив:



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

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



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

  • Пусть p0 и q0 - номера последних элементов участков, подвергшихся слиянию,

  • s0 - последний записанный в массив B элемент.

  • На каждом шаге слияния производится одно из двух действий:

  • B[s0+1]:=A[p0+1];

  • Inc(p0); Inc(s0);

  • или

  • B[s0+1]:=A[q0+1];{

  • Inc(q0); Inc(s0);



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

  • Первое действие может производиться при двух условиях:

  • первый отрезок не кончился

  • (p0 < q);

  • второй отрезок кончился (q0 = r) или не кончился, но элемент в нем не меньше

  • (q0 < r) и (A[p0+1] <= A[q0+1])



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

  • Окончательный текст

  • 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;



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

  • while (p0<>q) or (q0<>r) do

  • begin

  • if (p0

  • then begin

  • B[s0+1] := A[p0+1];

  • Inc(p0);

  • end

  • else begin B[s0+1] := A[q0+1]; Inc(q0);

  • end;

  • Inc(s0);

  • end;



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

  • t := r;

  • end {цикла t+k};

  • k := k *2;

  • A := B

  • End {цикла k};

  • example



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

  • Временная сложность

  • O(N*log(N))

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

  • сравнение



Похожие:

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

Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconАлгоритмы сортировки массивов. Сортировка является одной из фундаментальных алгоритмических задач программирования. Решению проблем, связанных с сортировкой, посвящено множество научных исследований, разработано множество алгоритмов.
Ключом сортировки называется атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом,...
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconУрок №3 в теме «предельные углеводороды»
Пары хлороформа имеют наркотическое воздействие, он токсичен для обмена веществ и для внутренних органов, особенно печени
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconСформировать представление о развитии и смене биогеоценозов. Сформировать представление о развитии и смене биогеоценозов
Познакомиться с понятием «экологическая сукцессия», её видами, природой и механизмом
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconЛекция №1 Вращательные кинематические пары. Поступательные кинематические пары
Поступательные кинематические пары обеспечивают только поступательное относительное движение
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconСортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >
Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (ключ сортировки)
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconЭтапы развития экономической теории
Общая черта экономической мысли Древнего мира состоит в стремлении сохранить приоритет натурального хозяйства, осудить с позиций...
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconАлгоритм Катхилла-Макки Основные определения
Граф можно представить себе состоящим из конечного множества узлов, или вершин, вместе с множеством ребер, которые по сути есть неупорядоченные...
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconПрограммирование на алгоритмическом языке бейсик норильск
Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий)...
Обменные сортировки: BubbleSort Алгоритм прямого обмена основывается на сравнении и смене позиций пары соседних элементов iconМетодика оформления алгоритма Алгоритм? Алгоритм! Алгоритм … мпэт чинилина И. Н
Процесс решения задачи представляется в виде последовательности простейших операций
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница