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

задачи
Простые алгоритмы сортировки
Сортировка выбором
Сортировка обменами
Сортировка вставками
Быстрая сортировка
Процедура разделения
Алгоритм QuickSort
Модификации
Анализ

упорядочен:
Sort (a, p, q) ≡ (∀ i: p ≤ i

вставка)

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

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

из a[i..n]}
k := i; min := a[i];
for j:=i+1 to

минимального элемента на i-ом шаге
(в сегменте из (n –

i-ом шаге,
включая обновления текущего минимума
(в

текущего минимума
на j-ом шаге внутреннего цикла = 1/j

суммарное число перестановок есть
Сортировка 10

2 do
1
i
n
Все наибольшие (упорядочены)
Остальные
(a[1..i] ≤ a(i..n]) & Sort (a, i+1,

обменами соседних элементов}
for j := 2 to i do
if a[j−1]

Сортировка 15

i -1)
Остальные
После i – го шага: Sort (a, 1, i)

& (x < a0[j..i-1]) & (a[j+1..i]=a0[j..i-1])
j := i;
while x

n

index=0..nMax;
index1=1..nMax;
index2=0..nMax+1;

index1; k: index1 );
{ сортировка массива методом вставки }

сравнений на i –ом шаге Ci = i/2 в среднем.
Тогда

среди a[1..i-1] }
x := a[i]; L:=1; R:=i;
while L≠R do
begin
m:=(L+R)

Сортировка 23

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

Сортировка

Partition


≤ x
> x
Инвариант цикла:



≤ x
> x
?
q
p
n


x
x
Условие завершения цикла

p

n

m m+1

m m+1

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

a : mass;

if a[q]

Сортировка 27

k: index1 );
var p, q: index2;

n, k );
if k>1 then { окончательная сортировка

<

<

<

<

<

<

4 5 6 7

5 6 7 8

о

И е О и н д а в

ч у я р п

п у ч р

я

д е в И а

и

н О

а

в

д И е

н

О

е д

И

д

е

р п

Сортировка 33

у

ч

р

п

число раз превосходят f (n) при достаточно большом n,
используется обозначение

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

менее чем в постоянное число раз превосходят f (n) при достаточно

же порядка, что и f (n) при достаточно большом n, используется