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

сортировки
Оптимальная сортировка
Поразрядная сортировка

на сравнениях и решающий задачу за меньшее число операций,
чем

O (n log n) при любых входных данных?

Сортировка с минимальным числом сравнений
(избыточные сравнения не выполняются)
Деревья решений (сравнений)
Для простоты – все ключи различны.
Основная операция сравнения: ki < kj

b, c
b → a, c
a → c → b
a

→ b → c

b → a → c

a → b
c↑

c → a → b,

b → a
c↑

b → c → a

c → b → a

n = 3, число перестановок и листьев = 3! = 6

да

нет

d
a → b
c, d
b → a
c, d
a →

b
d → c

b → a
c → d

n = 4, число перестановок и листьев = 4! = 24

a → b
c → d

b → a
d → c

→ b
c↑ a↑
a → c →

b → d

a → b → c → d

c → d → a → b

a → b → d
c↑

c → a → b → d

c → a → d → b

a → c → d → b

n = 4, число перестановок и листьев = 4! = 24

c → d → b
a↑

a → b
c → d

≥ число листьев ≥ n!
(число листьев должно быть не

менее числа исходов)
m ≥ ⎡log2 n!⎤

Итак, утверждение:
Для любого алгоритма сортировки, основанного на сравнениях, всегда можно подобрать такие исходные данные, что применение алгоритма потребует не менее ⎡log2 n!⎤ шагов.

= n log2 n – n log2 e + (1/2)

log2 n + O(1)

Итак, сложность задачи сортировки есть Ω (n log2 n),
а алгоритмы быстрой сортировки и пирамидальной сортировки решают задачу за время Θ (n log2 n)

достаточное для сортировки. S(n) ≥ ⎡log2 n!⎤. ?

S(n) = ⎡log2 n!⎤ ?
Например, S(5) = 7 (см.далее), а S(12) = 30 (!)

1-е сравнение: k1 : k2 → max(k1, k2)
2-е сравнение:

k3 : k4 → max(k3, k4)
3-е сравнение: max(k1, k2) : max(k3, k4)

e

b

d

c

a

сравнения
2 сравнения
1 или 2 сравнения

достоинство)
Масть: ♣ ‑ трефа, ♦ ‑ бубна, ♥ ‑ черва,

♠ ‑ пика
Достоинство: 2, 3, 4, 5, 6, 7, 8, 9, 10, В, Д, К, Т
Порядок по масти: ♣ < ♦ < ♥ < ♠.
Порядок по достоинству: 2<3<4<5<6<7<8<9<10<В<Д<К<Т

Порядок карт лексикографический:
♣2<♣3<♣4<♣5<♣6<♣7<♣8<♣9<♣10<♣В<♣Д<♣К<♣Т<
♦2<♦3<♦4<♦5<♦6<♦7<♦8<♦9<♦10<♦В<♦Д<♦К<♦Т<
♥2<♥3<♥4<♥5<♥6<♥7<♥8<♥9<♥10<♥В<♥Д<♥К<♥Т<
♠2<♠3<♠4<♠5<♠6<♠7<♠8<♠9<♠10<♠В<♠Д<♠К<♠Т

– распределяем по достоинству (раскладываем) на кучки («лицом» вверх)
2

В

3

Д

К

Т

4

5

6

7

8

9

10

Затем складываем

кучки друг на друга
(последовательно кучки большего достоинства сверху).
2 шаг – держим колоду рубашкой вниз и распределяем
на кучки по масти (карты кладем лицом вверх).
При этом в каждой «кучке по масти» карты лягут в порядке возрастания достоинства вниз кучки.

картами: ♣ < ♦ < ♥ < ♠

2 ♣

2 ♦

2

♠

2♥

Заключительный шаг – последовательно складываем, начиная справа, левую кучку на правую.

Задание: найти колоду карт и поупражняться

числа
в позиционной шестиричной системе счисления,
т.е. каждый разряд содержит цифры

0, 1, 2, 3, 4, 5
Например, пусть дана последовательность из 9 чисел
203, 045, 141, 405, 321, 522, 130, 054, 513
1 шаг – распределяем числа последовательности сначала по младшей цифре по ящикам с «именами»: «0», «1», «2», «3», «4», «5».
Ящики заполняются снизу вверх.

054, 513
Сцепляем последовательно слева направо содержимое ящиков в одну последовательность,

так, что нижнее число правого ящика следует за верхним числом левого соседнего ящика (внутри ящиков последовательность расположена снизу вверх). Таким образом, получим последовательность
130, 141, 321, 522, 203, 513, 054, 045, 405.
Заметим, что младшие цифры этой последовательности упорядочены по неубыванию.

045, 405
2 шаг – аналогичным образом распределяем по ящикам числа

полученной последовательности по средней цифре.

Повторяя сцепление содержимого ящиков, получим последовательность
203, 405, 513, 321, 522, 130, 141, 045, 054,
упорядоченную по двум младшим цифрам.

045, 054
3 шаг – аналогичным образом распределяем по ящикам числа

полученной последовательности по старшей цифре.

Повторяя сцепление содержимого ящиков, получим упорядоченную последовательность
045, 054, 130, 141, 203, 321, 405, 513, 522.

x2, x3,…, xn.
Каждый ключ состоит из p разрядов:
( ∀ i ∈1..n: xi = (xi(p), xi(p−1),…, xi(1))

),
а каждый q-й разряд представлен цифрой xi(q) ∈0..r−1.
Тогда
(xi < xj) ↔ 
(∃ t ∈1..p: (∀ q ∈ t + 1..p: xi(q) = xj(q)) & (xi(t) < xj(t))).

новую последовательность используем очереди:

Q – общая очередь (исходная, промежуточные и

результирующая последовательности);
q[0], q[1],…, q[r − 1] – очереди по каждой r-ичной цифре («ящики»).

Empty(q[k]) od;
while not Null(Q) do
x ← Q;
Пусть x = (x(p), x(p−1),…, x(1)), тогда
q[x(j)] ← x
od {while};
Q ← сцепление(q[0], q[1],…, q[r − 1])
od {for

j}

выполняется p раз.
Каждая итерация этого цикла для каждого из

n чисел выполняет извлечение и запись в очередь, т.е. всего 2n таких операций.
Кроме того, на каждой итерации происходит r − 1 сцепление очередей.
Таким образом на одной итерации требуется 2n + r − 1 операций,
а всего по всем разрядам O (p n + p r ) операций.

Сравнение с O ( n log n ) !...