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




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


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

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

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






Алгоритм BubbleSort( a, n);

  • Алгоритм 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;



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

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

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



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

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

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

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

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

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



Алгоритм ShakerSort (a,n);

  • Алгоритм 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;



for j ← L to R do {слева направо}

  • 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



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

  • (n2-n)/2

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

  • 3(n2-n)/2



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

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

  • Cmin = n—1

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



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

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

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

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

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

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



  • 1

  • i< k < n: х  Ak





Алгоритм partition (a,1,n,x);

  • Алгоритм 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<=j then w ← a[i]; a[i] ← a[j];

  • a[j] ← w; i++; j--

  • while i



  • Алгоритм 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

  • Начало рекурсии - Sort (1,n)







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

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

  • (n-1)/6

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

  • n*logn

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

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



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

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

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

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



for i := 0 to M do

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



Divide et impera [дивидэ эт импэра]

  • Divide et impera [дивидэ эт импэра]

  • Парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче.

  • Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.



“Разделяй и властвуй”

  • “Разделяй и властвуй”

  • Разделение (декомпозиция) задачи на несколько подзадач.

  • Покорение — рекурсивное решение этих подзадач. Когда объем подзадачи достаточно мал, выделенные подзадачи решаются непосредственно.

  • Комбинирование решения исходной задачи из решений вспомогательных задач.



Алгоритм сортировки слиянием (merge sort)

  • Алгоритм сортировки слиянием (merge sort)

  • Разделение: сортируемая последовательность, состоящая из n элементов, разбивается на две меньшие последовательности, каждая из которых содержит n/2 элементов

  • Покорение: сортировка обеих вспомогательных последовательностей методом слияния

  • Комбинирование: слияние двух отсортированных последовательностей для получения окончательного результата



Процедура Merge (A,p, q,r),

  • Процедура Merge (A,p, q,r),

  • где А — массив, а р, q и r — индексы, нумерующие элементы массива, такие, что р ≤ q < r.

  • В этой процедуре предполагается,

  • что элементы подмассивов A [p..q] и A[q+1..r] упорядочены.

  • Она сливает эти два подмассива в один отсортированный, элементы которого заменяют текущие элементы подмассива А [р..r].















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

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

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

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

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

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



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

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

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



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

  • Процедура преобразования 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 - номера последних элементов участков, подвергшихся слиянию,

  • Пусть 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

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

  • t := r;

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

  • k := k *2;

  • A := B

  • End {цикла k};

  • example



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

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

  • O(N*log(N))

  • (так как преобразование

  • k-упорядоченного массива в

  • 2k-упорядоченный требует порядка

  • N действий и внешний цикл по k совершает порядка log(N) итераций).

  • сравнение



Похожие:

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


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