Структуры и алгоритмы обработки данных 2

Содержание

Слайд 2

Сортировка 2 Дан массив a: array [1..n] of Ordinal Отрезок (сегмент)

Сортировка 2

Дан массив a: array [1..n] of Ordinal
Отрезок (сегмент) массива a[p..q] упорядочен:
Sort

(a, p, q) ≡ (∀ i: p ≤ i < q: a[i] ≤ a[i+1])
Предусловие: a[1..n] = a0[1..n]
Постусловие: Sort (a, 1, n) & & Перестановка(a[1..n], a0[1..n]),
где Перестановка(a[1..n], a0[1..n]) ≡
(∀ i: 1 ≤ i ≤ n: (N j: 1 ≤ j ≤ n: a[ i ] = a0[ j ] ) =
= (N j: 1 ≤ j ≤ n: a[ i ] = a [ j ] ) )
Слайд 3

Сортировка 3 Простые алгоритмы сортировки Сортировка выбором Идея. Пример. Список (удаление

Сортировка 3

Простые алгоритмы сортировки
Сортировка выбором
Идея. Пример.
Список (удаление и вставка)

Устойчивость сортировки

– сохранение относительного порядка элементов с равными ключами
Слайд 4

Сортировка 4 Сортировка выбором. Пример. Массив (обмен элементов).

Сортировка 4

Сортировка выбором.
Пример.
Массив (обмен элементов).

Слайд 5

Сортировка 5 Простые алгоритмы сортировки Сортировка выбором Инвариант внешнего цикла: Все

Сортировка 5

Простые алгоритмы сортировки
Сортировка выбором
Инвариант внешнего цикла:

Все наименьшие (упорядочены)

Остальные

1

i

n

(a[1..i) ≤ a[i..n])

& Sort (a, 1, i −1) & (1 ≤ i ≤ n)
Если во внутреннем цикле ищем первое вхождение минимума, то сортировка в списке устойчивая, а в массиве неустойчивая
Слайд 6

Сортировка 6 Сортировка выбором for i:=1 to n−1 do begin {поиск

Сортировка 6

Сортировка выбором
for i:=1 to n−1 do
begin
{поиск минимума из a[i..n]}
k :=

i; min := a[i];
for j:=i+1 to n do
if a[j] < min then
begin k := j; min := a[k] end;
{обмен a[k] ↔ a[i] }
a[k] := a[i]; a[i] := min
end {for}
Слайд 7

Сортировка 7 Анализ сортировки выбором Сi – число сравнений при выборе

Сортировка 7

Анализ сортировки выбором
Сi – число сравнений при выборе минимального элемента

на i-ом шаге
(в сегменте из (n – i + 1) элементов)
Сi = n – i
Суммарно по всем шагам:
Слайд 8

Сортировка 8 Анализ сортировки выбором Пусть Mi – число перестановок на

Сортировка 8

Анализ сортировки выбором
Пусть Mi – число перестановок на i-ом шаге,


включая обновления текущего минимума
(в сегменте из (n – i + 1) элементов).
В худшем случае
(обратно упорядоченный массив):
Mi =(n – i) + 3
Тогда суммарно по всем шагам (i∈1..n−1):
Mmax= (n2 – n)/2 + 3(n – 1)
Слайд 9

Сортировка 9 Анализ сортировки выбором В среднем: Вероятность того, что произойдет

Сортировка 9

Анализ сортировки выбором
В среднем:
Вероятность того, что произойдет обновление
текущего минимума

на j-ом шаге внутреннего цикла = 1/j
(любой, в том числе последний из j элементов - минимальный).
Т.о. за i-й шаг среднее (М.О.) число перестановок
= 1/2 + 1/3 + 1/4 +… + 1/(n-i+1) = Hn-i+1 -1,
где частичная сумма гармонического ряда
Hk= 1 + 1/2 + 1/3 + … + 1/k,
Hk= ln k + γ + 1/(2k) +... , где γ - постоянная Эйлера.
Итак, за i-й шаг внешнего цикла среднее число присваиваний Hn-i+1 -1+3= Hn-i+1 +2 ≈ ln (n-i+1) + γ +2
Слайд 10

Анализ сортировки выбором в среднем В среднем за весь внешний цикл

Анализ сортировки выбором в среднем
В среднем за весь внешний цикл суммарное

число перестановок есть

Сортировка 10

Слайд 11

Сортировка 11 Простые алгоритмы сортировки Сортировка обменами («пузырьковая»)

Сортировка 11

Простые алгоритмы сортировки
Сортировка обменами («пузырьковая»)

Слайд 12

Сортировка 12 Простые алгоритмы сортировки Сортировка обменами («пузырьковая») Продолжение

Сортировка 12

Простые алгоритмы сортировки
Сортировка обменами («пузырьковая»)
Продолжение

Слайд 13

Сортировка 13 Простые алгоритмы сортировки Сортировка обменами («пузырьковая») Продолжение

Сортировка 13

Простые алгоритмы сортировки
Сортировка обменами («пузырьковая»)
Продолжение

Слайд 14

Сортировка 14 Простые алгоритмы сортировки Сортировка обменами Инвариант внешнего цикла For

Сортировка 14

Простые алгоритмы сортировки
Сортировка обменами
Инвариант внешнего цикла
For i:=n downto 2 do

1

i

n

Все

наибольшие (упорядочены)

Остальные

(a[1..i] ≤ a(i..n]) & Sort (a, i+1, n) & (1 ≤ i ≤ n)

Слайд 15

Сортировка обменами (пузырьковая) for i:=n downto 2 do begin {просмотр a[1..i]

Сортировка обменами (пузырьковая)
for i:=n downto 2 do
begin
{просмотр a[1..i] с обменами

соседних элементов}
for j := 2 to i do
if a[j−1] > a[j] then a[j−1] ↔ a[j] ;
{a[i] = max a[1..i] }
end

Сортировка 15

Слайд 16

Анализ сортировки обменами (пузырьковой) Сортировка 16

Анализ сортировки обменами (пузырьковой)

Сортировка 16

Слайд 17

Сортировка 17 Простые алгоритмы сортировки Сортировка вставками (включением)

Сортировка 17

Простые алгоритмы сортировки
Сортировка вставками (включением)

Слайд 18

Сортировка 18 Простые алгоритмы сортировки Сортировка ВСТАВКАМИ Инвариант внешнего цикла: 1

Сортировка 18

Простые алгоритмы сортировки
Сортировка ВСТАВКАМИ
Инвариант внешнего цикла:

1

i

n

Упорядочены:
Sort (a, 1, i -1)

Остальные

После

i – го шага: Sort (a, 1, i)
Слайд 19

Сортировка прямыми ВСТАВКАМИ Сортировка 19 j −1 0 1 x j

Сортировка прямыми ВСТАВКАМИ

Сортировка 19

j −1

0

1

x

j

i

x

x

Sort (a, 1, i -1) & (x

< a0[j..i-1]) & (a[j+1..i]=a0[j..i-1])

j := i;
while x < a[j -1] do
begin a[j] := a[j -1]; j := j -1 end
{ (x ≥ a[j -1]) & (x < a [j+1..i]) & (a[j] – «свободен»)}
a[j] := x;

n

Слайд 20

Сортировка 20 Простые алгоритмы сортировки Сортировка ВСТАВКАМИ АЛГОРИТМ Прямые вставки (StraightInsertion)

Сортировка 20

Простые алгоритмы сортировки
Сортировка ВСТАВКАМИ
АЛГОРИТМ Прямые вставки (StraightInsertion)
type index=0..nMax;
index1=1..nMax;

index2=0..nMax+1;
mass=array [index] of Integer;
Слайд 21

Сортировка 21 procedure StraightInsertion ( var a: mass; n: index1; k:

Сортировка 21

procedure StraightInsertion ( var a: mass; n: index1; k:

index1 );
{ сортировка массива методом вставки }
var i: index;
j: index1;
x: Integer;
begin
for i:=2 to n do
begin { включить a[i] на соотв. место в a[1..i] }
x := a[i]; a[0] := x; { a[0] - "барьер" }
j := i;
while x < a[j-1] do
begin { 1<=j<=i }
a[j] := a[j-1];
j := j-1
end { while };
a[j] := x
end { for }
end { StraightInsertion };
Слайд 22

Сортировка 22 Сортировка ПРЯМЫМИ ВСТАВКАМИ Анализ Число сравнений ≈ число перемещений.

Сортировка 22

Сортировка ПРЯМЫМИ ВСТАВКАМИ
Анализ
Число сравнений ≈ число перемещений.
Число сравнений на

i –ом шаге Ci = i/2 в среднем.
Тогда по всем шагам i∈2..n
Слайд 23

Сортировка БИНАРНЫМИ ВСТАВКАМИ for i:=2 to n do begin { Найти

Сортировка БИНАРНЫМИ ВСТАВКАМИ
for i:=2 to n do
begin
{ Найти место a[i] среди

a[1..i-1] }
x := a[i]; L:=1; R:=i;
while L≠R do
begin
m:=(L+R) div 2;
if a[m] < x then L:=m+1 else R:=m
end; {(L∈1..i) & (a[L-1] < x ≤ a[L])}
{сдвинуть a[L..i-1] на позицию вправо на место a[L+1..i]}
for j:=i downto L+1 do a[j] := a[j-1];
{вставить x на место a[L]}
a[L]:=x
end {for}

Сортировка 23

Слайд 24

Сортировка БИНАРНЫМИ ВСТАВКАМИ Анализ алгоритма Число сравнений на i –ом шаге

Сортировка БИНАРНЫМИ ВСТАВКАМИ Анализ алгоритма
Число сравнений на i –ом шаге Ci

≤ ⎡log2i⎤.
По всем шагам (i∈2..n)

Сортировка 24

Слайд 25

Сортировка 25 Быстрая сортировка (QuickSort) Основа – процедура разделения Partition ≤

Сортировка 25

Быстрая сортировка (QuickSort)

Основа – процедура разделения Partition

≤ x

> x

Инвариант

цикла:

≤ x

> x

?

q

p

n

x

x

Условие завершения цикла p + 1 = q

p

n

m m+1

m m+1

& (m < q ≤ p + 1 ≤ n + 1)

Слайд 26

Сортировка 26 Быстрая сортировка (QuickSort) procedure Partition1 ( var a :

Сортировка 26

Быстрая сортировка (QuickSort)

procedure Partition1 ( var a : mass;

m, n: index1; var p: index2);
var x, y: integer;
mn2, q: index2;
begin { m < n }
mn2:=(m+n) div 2;
x := a[mn2]; a[mn2]:= a[m]; a[m]:=x;
q := m+1; p := n;
{ inv: (m (ALL k: m<=kx)}
Слайд 27

while q begin if a[q] else if a[p] > x then

while q<= p do
begin
if a[q] <= x

then q := q+1
else
if a[p] > x then p := p-1
else { a[p]<= x < a[q] }
begin
y := a[p];
a[p] := a[q];
a[q] := y;
q := q+1;
p := p-1
end { if };
end { while };
a[m] := a[p];
a[p] := x;
end { Partition1 };

Сортировка 27

Слайд 28

Быстрая сортировка: разделение и слияние Сортировка 28 Partition1

Быстрая сортировка:
разделение и слияние

<

<

<

<

<

<

<

<

<

<

Сортировка 28

Partition1

<

Слайд 29

Сортировка 29 procedure Sortp1 (var a: mass; m, n: index1; k:

Сортировка 29

procedure Sortp1 (var a: mass; m, n: index1; k: index1

);
var p, q: index2;
begin
Partition1 ( a, m, n, p );
if p-m>k then Sortp1 ( a, m, p-1, k );
q:=p+1;
if n-q+1>k then Sortp1 ( a, q, n, k )
{ подмассив длиной <= k не сортируем !
1<=k<=50 , при k=1 - полная сортировка }
end { Sortp1 };
Слайд 30

Сортировка 30 begin { QuickSort1 } Sortp1( a, 1, n, k

Сортировка 30

begin { QuickSort1 }
Sortp1( a, 1, n, k );

if k>1 then { окончательная сортировка
простым методом }
StraightInsertion ( a, n ,1)
end { QuickSort1 };

<

<

<

<

<

<

Слайд 31

Быстрая сортировка Неполная сортировка. Выбор k Сортировка 31 k kмин t

Быстрая сортировка
Неполная сортировка. Выбор k

Сортировка 31

k

kмин

t

Слайд 32

Первый вызов Partition 32 1 2 3 4 5 6 7

Первый вызов Partition 32

1 2 3 4 5 6 7 8 9

10 11 12 13 14
у п О р я д о ч И в а н и е
о п О р я д у ч И в а н и е
о е О р я д у ч И в а н и п
о е О р я д у ч И в а н и п
о е О и я д у ч И в а н р п
о е О и н д у ч И в а я р п
о е О и н д у ч И в а я р п
о е О и н д а ч И в у я р п
о е О и н д а в И ч у я р п
И е О и н д а в о ч у я р п
Слайд 33

1 2 3 4 5 6 7 8 9 10 11

1 2 3 4 5 6 7 8 9 10 11

12 13 14
И е О и н д а в о ч у я р п

о

И е О и н д а в

ч у я р п

п у ч р

я

д е в И а

и

н О

а

в

д И е

н

О

е д

И

д

е

р п

Сортировка 33

у

ч

р

п

Слайд 34

Сортировка 34 Анализ. Лучший случай Быстрая сортировка (QuickSort) n/2 n n/2

Сортировка 34

Анализ. Лучший случай

Быстрая сортировка (QuickSort)

n/2

n

n/2

n/4

n/4

n/4

n/4

n/8

n/8

n/8

n/8

n/8

n/8

n/8

n/8

n log2n

1

1

1

1

1

1

Слайд 35

Сортировка 35 Анализ. Худший случай Быстрая сортировка (QuickSort) n n-1 n-2

Сортировка 35

Анализ. Худший случай

Быстрая сортировка (QuickSort)

n

n-1

n-2

1

1

1

n-3

n-4

1

1

1

Слайд 36

Сортировка 36 Быстрая сортировка (QuickSort) Анализ. Промежуточный случай

Сортировка 36

Быстрая сортировка (QuickSort)

Анализ. Промежуточный случай

Слайд 37

Анализ. В среднем Сортировка 37 Быстрая сортировка (QuickSort) i 1 n

Анализ. В среднем

Сортировка 37

Быстрая сортировка (QuickSort)

i

1

n

Слайд 38

Анализ. В среднем (продолжение) Сортировка 38 Быстрая сортировка (QuickSort)

Анализ. В среднем (продолжение)

Сортировка 38

Быстрая сортировка (QuickSort)

Слайд 39

Анализ. В среднем (продолжение) Сортировка 39 Быстрая сортировка (QuickSort)

Анализ. В среднем (продолжение)

Сортировка 39

Быстрая сортировка (QuickSort)

Слайд 40

Для указания множества функций, которые не более чем в постоянное число

Для указания множества функций,
которые не более чем в постоянное число

раз превосходят f (n) при достаточно большом n,
используется обозначение О(f(n)).
Запись g (n) ∈ О(f(n)) означает, что
cуществуют:
вещественная константа C > 0 и
натуральная константа n0 ,
для которых g (n) ≤ C f (n) при всех n ≥ n0

Приложение Асимптотические оценки Обозначения О(f(n)), Ω(f(n)), Θ(f(n))

Слайд 41

Асимптотические оценки Обозначение О(f(n)) g(n) C f(n) n0 n

Асимптотические оценки Обозначение О(f(n))

g(n)

C f(n)

n0

n

Слайд 42

Асимптотические оценки Обозначения О(f(n)), Ω(f(n)), Θ(f(n)) Для указания множества функций, которые

Асимптотические оценки Обозначения О(f(n)), Ω(f(n)), Θ(f(n))

Для указания множества функций,
которые не менее

чем в постоянное число раз превосходят f (n) при достаточно большом n, используется обозначение Ω(f(n)).
Запись g (n) ∈ Ω(f(n)) означает, что
существуют :
вещественная константа C > 0 и
натуральная константа n0 ,
для которых g (n) ≥ C f (n) при всех n ≥ n0.
Слайд 43

Асимптотические оценки Обозначение Ω(f(n)) g(n) C f(n) n0 n

Асимптотические оценки Обозначение Ω(f(n))

g(n)

C f(n)

n0

n

Слайд 44

Асимптотические оценки Обозначения О(f(n)), Ω(f(n)), Θ(f(n)) Для указания множества функций того

Асимптотические оценки Обозначения О(f(n)), Ω(f(n)), Θ(f(n))

Для указания множества функций того же

порядка, что и f (n) при достаточно большом n, используется обозначение Θ(f(n))
Запись g (n) ∈  Θ(f(n)) означает, что
существуют :
вещественные константы C1 > 0 и C2 > 0 и
натуральная константа n0 , для которых
C1 f (n) ≤ g (n) ≤ C2 f (n) при всех n ≥ n0
- Предыдущая
Структуры и алгоритмы обработки данных
Следующая -
Частичное упрядочение

Похожие презентации

Презентация "Рынок факторов производства: рынок земли" - скачать презентации по Экономике
Внутреннее убранство православного храма
Числовые характеристики одномерных и двумерных случайных величин
To Pouring Pattern Stripping &amp; return Manipulator on jib crane Pattern Change
Массовая и элитарная культура
Технологические циклы
глагол to be
Материально-техническое обеспечение спортивных сооружений. Протезы
Становление белорусской государственности
Шаблон презентации
Презентация по МХК Боги древнего Египта
Качество и сертификация
Асбестовский экономический колледж. Итоговая квалификационная работа. Направление(специальность):Оператор ПЭВМ (72)
Чередующиеся корни
Виды кадровой политики
Бенджамин Франклин
Тест
Бизнес-план компании «Монолит» - производство строительных материалов. Проект по экономике и экономической географии ученика
Мастер класс “С чего начать: Подготовка и создание архивов открытого доступа» Ирина Кучма, менеджер программы Открытый доступ, eIFL.net Презентация на совместном семинаре eIFL.net и ГПНТБ России «Открытый доступ и открытые архивы информации», 11 июня
Рак легкого
Презентация____
Синтоизм и его суть
Изменение имён прилагательных по родам - презентация для начальной школы__________________________________________________________________________________________________________
Тема 1.3 Основы организации и нормирования труда ЧАСТЬ 2 нормирование труда
Разрезы и их виды в чертежах
Дополнительные взыскания и порядок их применения по трудовому законодательству РФ
Ремонт и обслуживание тепловентилятора
Сінтаксіс і пунктуацыя. Сказы з параўнальнымі зваротамі
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть