Слайд 2Понятие
Сортировать - распределять, разбирать по сортам, качеству, размерам, по сходным признакам. (толковый
![Понятие Сортировать - распределять, разбирать по сортам, качеству, размерам, по сходным признакам.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-1.jpg)
словарь Ожегова)
синонимы: классификация, систематизация.
перегруппировка элементов в некотором определенном порядке (упорядочивание, ранжирование).
Слайд 3Классы сортировок
сортировка массивов
сортировка (последовательных) файлов.
или
внутренняя сортировка
внешняя сортировка
![Классы сортировок сортировка массивов сортировка (последовательных) файлов. или внутренняя сортировка внешняя сортировка](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-2.jpg)
Слайд 4Определение
Частичным порядком на множестве S называется такое бинарное отношение R, что для
![Определение Частичным порядком на множестве S называется такое бинарное отношение R, что](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-3.jpg)
любых а, b и с из S
aRa (R рефлексивно),
aRb и bRc => aRc (R транзитивно),
aRb и bRa => a=b (R антисимметрично).
Слайд 5Определение
Линейным, или полным, порядком на множестве S называется такой частичный порядок R
![Определение Линейным, или полным, порядком на множестве S называется такой частичный порядок](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-4.jpg)
на S, что для любых двух элементов a, b выполняется либо aRb, либо bRa (другими словами, элементы a, b сравнимы)
Слайд 6Задача сортировки
Пусть дана последовательность из n элементов а1 , а2 , …
![Задача сортировки Пусть дана последовательность из n элементов а1 , а2 ,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-5.jpg)
, аn , выбранных из множества, на котором задан линейный порядок.
элемент аi назовем записью,
линейный порядок будем обозначать ≤
Каждая запись аi имеет ключ ki , который управляет процессом сортировки.
помимо ключа, запись может иметь некоторую дополнительную информацию, которая не влияет на процесс сортировки, но всегда присутствует в этой записи.
Слайд 7Задача сортировки
Требуется найти такую перестановку π = (π(1), π(2),…, π(n)) этих n
![Задача сортировки Требуется найти такую перестановку π = (π(1), π(2),…, π(n)) этих](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-6.jpg)
записей, после которой ключи расположились бы в неубывающем порядке:
k π (1) ≤ k π(2) ≤… ≤ k π(n)
Слайд 8Определение
Алгоритм сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов одинаковыми
![Определение Алгоритм сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-7.jpg)
ключами не изменяется предполагается, что элементы уже были отсортированы по некоторому вторичному ключу)
π(i) < π(j), если k π (i) ≤ k π(j) и i < j.
Слайд 9Сортировки
Все алгоритмы сортировки можно разбить на три группы:
сортировка с помощью включения,
![Сортировки Все алгоритмы сортировки можно разбить на три группы: сортировка с помощью](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-8.jpg)
сортировка выбором,
сортировка с помощью обменов
Слайд 10Сортировка с помощью включения
Пусть элементы а1 , а2 , … , аi-1
![Сортировка с помощью включения Пусть элементы а1 , а2 , … ,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-9.jpg)
, ; 1 < i ≤ n уже упорядочены на предыдущих этапах данным алгоритмом.
На очередном этапе необходимо взять элемент аi , и включить в нужное место уже упорядоченной последовательности а1 , а2 , … , аi-1 .
Слайд 11Сортировка с помощью включения
В зависимости от того, как происходит процесс включения элемента,
![Сортировка с помощью включения В зависимости от того, как происходит процесс включения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-10.jpg)
различаю прямое включение и двоичное включение.
Слайд 12Алгоритм сортировки с помощью прямого включения
Алгоритм insertion (a, n);
Input: массив
![Алгоритм сортировки с помощью прямого включения Алгоритм insertion (a, n); Input: массив](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-11.jpg)
А, содержащий n чисел (n≥1).
Output: упорядоченный массив A.
for i ← 2 to n {
x ← a[i]; a[0] ← x; j ← i;
while (x.key < a[j-1].key) {
a[j] ← a[j-1]; j ← j-1
}
a[j] ← x;
}
Слайд 15Алгоритм двоичного включения
Алгоритмinsertion2(a, n);
for i ← 2to n{
x ← a[i]; L
![Алгоритм двоичного включения Алгоритмinsertion2(a, n); for i ← 2to n{ x ←](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-14.jpg)
←1; R ← i;
while (L < R) {
m=[(L+R)/2];
if (a[m].key< x.key) {L ←m + 1}
else R ←m;
}
for j ←i downto (R + 1){
a[j] ←a[j -1];}
a[R] ← x;
}
Слайд 17Сортировка выбором
Идея сортировки заключается в следующем:
1.Выбрать элемент с наименьшим ключом и поменять
![Сортировка выбором Идея сортировки заключается в следующем: 1.Выбрать элемент с наименьшим ключом](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-16.jpg)
его с первым элементом. Теперь первый элемент стоит на своем месте.
2.Повторить действия с оставшимися n-1 элементами.
3.Процесс заканчивается, когда n -1 элементов будут помещены на свои места.
Слайд 18Сортировка выбором
Алгоритм selection (a, n);
for i ← 1to n-1{
k ← i;
for
![Сортировка выбором Алгоритм selection (a, n); for i ← 1to n-1{ k](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-17.jpg)
j ← i+1to n{
if a[j].key< a[k].key {
k ← j;
}
a[i]↔a[k];
}
Слайд 19Оценка трудоемкости алгоритма
В худшем случае:
T(n)=Cn+T(n-1), T(1)=0;
T(n)=Θ(n2)
![Оценка трудоемкости алгоритма В худшем случае: T(n)=Cn+T(n-1), T(1)=0; T(n)=Θ(n2)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-18.jpg)
Слайд 20Сортировка с помощью обменов
Сортировки помощью обменов основываются на сравнении двух элементов.
Если порядок
![Сортировка с помощью обменов Сортировки помощью обменов основываются на сравнении двух элементов.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-19.jpg)
элементов не соответствует упорядоченности, то происходит их обмен.
Процесс повторяется до тех пор, пока элементы не будут упорядочены.
Слайд 21Сортировка с помощью обменов
Пузырьковая сортировка
Шейкерная сортировка
![Сортировка с помощью обменов Пузырьковая сортировка Шейкерная сортировка](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-20.jpg)
Слайд 22Пузырьковая сортировка
Просматриваем исходную последовательность справа налево и на каждом шаге меньший из
![Пузырьковая сортировка Просматриваем исходную последовательность справа налево и на каждом шаге меньший](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-21.jpg)
двух соседних элементов перемещается в левую позицию.
В результате первого просмотра самый маленький элемент будет находиться в крайней левой позиции.
После чего повторяем описанный выше процесс, рассматривая в качестве исходной последовательности массив, начиная со 2-ой позиции и т.д.
Слайд 23Пузырьковая сортировка
Алгоритм bubble_sort (a, n);
for i ← 2to n {
for j
![Пузырьковая сортировка Алгоритм bubble_sort (a, n); for i ← 2to n {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-22.jpg)
← n downto i {
if (a[j-1].key> a[j].key){
a[j-1]↔a[j];
}
}
}
Слайд 24Шейкерная сортировка
Анализ алгоритма пузырьковой сортировки приводит к следующим наблюдениям:
Если при некотором из
![Шейкерная сортировка Анализ алгоритма пузырьковой сортировки приводит к следующим наблюдениям: Если при](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-23.jpg)
проходов нет перестановок, то алгоритм можно завершить.
Если зафиксировать индекс k последнего обмена (все пары левее этого индекса уж упорядочены), то просмотр можно завершить на этом индексе, а не идти до нижнего предела для индекса i.
Чередование направлений для просмотра (всплываетсамый легкий,тонет самый тяжелый).
Слайд 25Шейкерная сортировка
Алгоритм shaker_sort (a, n);
L ← 2; R ← n; k ←
![Шейкерная сортировка Алгоритм shaker_sort (a, n); L ← 2; R ← n;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-24.jpg)
n;
repeat
for j ← Rdown to L
if (a[j-1].key> a[j].key){
a[j-1]↔a[j]; k ← j;
}
L ← k+1;
for j ← Lto R
if (a[j-1].key> a[j].key){
a[j-1]↔a[j]; k ← j;
}
R ← k-1;
until (L>R);
Слайд 26Сортировка слиянием
Сортировка слиянием заключается в следующем:
1.Делим последовательность элементов на две части;
2.Сортируем отдельно
![Сортировка слиянием Сортировка слиянием заключается в следующем: 1.Делим последовательность элементов на две](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-25.jpg)
каждую из частей;
3.Производим слияние отсортированных частей последовательности:
a)при слиянии сравниваем наименьшие элементы и меньший из них отправляем в список вывода;
b)повторяем описанные действия до тех пор, пока не исчерпается одна из частей;
c)все оставшиеся элементы другой части пересылаем в список вывода.
Слайд 27Процедура слияния отсортированных частей последовательности
Алгоритм merge (a, L, Z, R);
i ← L;
![Процедура слияния отсортированных частей последовательности Алгоритм merge (a, L, Z, R); i](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-26.jpg)
j ← Z+1; k ← 1;
while (i ≤ Z) &(j ≤R){
if (a[i].key< a[j].key){
c[k]←a[i]; i++; k++;}
else {
c[k]← a[j]; j++; k++;}
}
while (i ≤ Z) {
c[k]←a[i]; i++; k++;}
while (j ≤R){
c[k]←a[j]; j++; k++;}
k ← 0
for i ← L to R {
k++; a[i] ← c[k];}
Слайд 28Сортировка слиянием
Алгоритм merge_sort (L, R);
if (L ≠ R ){
k ← (L+R)
![Сортировка слиянием Алгоритм merge_sort (L, R); if (L ≠ R ){ k](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-27.jpg)
div 2;
merge_sort(L, k);
merge_sort(k+1, R);
merge (a, L, k, R);
}
Слайд 29Быстрая сортировка (Хоара)
Суть алгоритма состоит в следующем:
1.Выбрать некоторый элемент х для сравнения
![Быстрая сортировка (Хоара) Суть алгоритма состоит в следующем: 1.Выбрать некоторый элемент х](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-28.jpg)
(это может быть средний, первый или последний элемент)
2.Используя обмены, выполнить процедуру разделения, суть которой заключается следующем: разбить массив на две части: левую с ключами ≤х и правую с ключами ≥х.
Слайд 30Быстрая сортировка
Данные действия могу быть выполнены, например, следующим алгоритмом:
просматриваем массив слева, пока
![Быстрая сортировка Данные действия могу быть выполнены, например, следующим алгоритмом: просматриваем массив](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-29.jpg)
не встретим элемент а[i]> х
просматриваем массив справа, пока не встретим элемент а[j] < x
меняем местами эти два элемента
продолжаем просмотр обмен до тех пор, пока не буду просмотрены все элементы массива (i> j).
Повторяем процедуру разделения к получившимся двум частям, затем частям частей так далее, пока каждая из частей не будет состоять из одного единственного элемента
Слайд 31Быстрая сортировка
Алгоритм quick_sort (L, R);
x ← a[(L+R) div 2]; i ← L;
![Быстрая сортировка Алгоритм quick_sort (L, R); x ← a[(L+R) div 2]; i](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-30.jpg)
j ← R;
repeat{
while (a[i].key < x.key) {i++;}
while (a[j].key> x.key) {j--;}
if (i ≤ j) {
a[i] ↔ a[j]; i++; j--;}
} until (i ≥ j)
if (L < j) {quick_sort(L, j);}
if (i < R) {quick_sort(i, R);}
Слайд 32Оценка сложности алгоритма
Процедура разделения n элементов требует Cn операций, так как каждый
![Оценка сложности алгоритма Процедура разделения n элементов требует Cn операций, так как](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-31.jpg)
элемент последовательности необходимо сравнить с выбранным элементом, поэтом рекуррентное уравнение будет иметь вид:
T(n) = Cn+ T(|A1|)+T(|A2|),
где |A1|, |A2| -размеры левой и правой части массива после процедуры разделения.
Если предположить, что разделение в среднем разбивает часть пополам то
Т(n) = Сn+ 2Т(n/2), T(n)= Θ(nlogn).
Слайд 33Оценка сложности алгоритма
Худшим случаем является ситуация, когда в качестве сравниваемого элемента выбирается
![Оценка сложности алгоритма Худшим случаем является ситуация, когда в качестве сравниваемого элемента](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-32.jpg)
наибольший из всех элементов рассматриваемой части. В этом случае после процедуры разделения |А1|= n–1, |А2|= 1.
Рекуррентное уравнение будет иметь вид
Т(n) = Сn+ Т(n-1) + Т(1), T(n)=Θ(n2)
Cам Ч. Хоар предполагает, что х надо выбирать случайно, а для небольших выборок останавливаться на медиане.
Слайд 34Пример
Фиксируем элемент x = 7 (средний)
![Пример Фиксируем элемент x = 7 (средний)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-33.jpg)
Слайд 39Порядковые статистики
Задача: дано множество из n чисел. Найти тот его элемент, который
![Порядковые статистики Задача: дано множество из n чисел. Найти тот его элемент,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-38.jpg)
будет k-м по счёту, если расположить элементы множества в порядке возрастания.
В англоязычной литературе такой элемент называется k-й порядковой статистикой (order statistic).
Например, минимум (minimum) - это порядковая статистика номер 1, а максимум (maximum) - порядковая статистика номер п.
Слайд 40Порядковые статистики
Медианой (median) называется элемент множества, находящийся (по счёту) посередине между минимумом
![Порядковые статистики Медианой (median) называется элемент множества, находящийся (по счёту) посередине между](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-39.jpg)
и максимумом. Точнее говоря, если п нечётно, то медиана - это порядковая статистика номер i = (n + 1)/2, а если n четно, то медиан даже две: с номерами i = n/2 и i = n/2 + 1.
Можно ещё сказать, что, независимо от чётности n, медианы имеют номер i = [(n+1)/2]
В дальнейшем мы будем называть медианой меньшую из двух (если их две).
Слайд 41Порядковые статистики
Пример: 18 24 12 27 19
Медиана =19
Поиск медианы является
![Порядковые статистики Пример: 18 24 12 27 19 Медиана =19 Поиск медианы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-40.jpg)
частным случаем более общей задачи:
нахождение k-го наименьшего элемента из n элементов
Слайд 42Выбор элемента с данным номером
Дано: Множество А из n различных элементов и
![Выбор элемента с данным номером Дано: Множество А из n различных элементов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-41.jpg)
целое число k, 1 < k < n.
Найти: Элемент х из А, для которого ровно k-1 элементов множества A меньше х.
Эту задачу можно решить за время Θ(n lg n): отсортировать числа, после чего взять k-й элемент в полученном массиве.
Однако, есть и более быстрые алгоритмы.
Рассмотрим алгоритм для нахождения k-го наименьшего элемента из n элементов, предложенный Ч. Хоаром
Слайд 43Выбор элемента с k номером (A1)
Выполняется операция разделения на отрезке [L, R],
![Выбор элемента с k номером (A1) Выполняется операция разделения на отрезке [L,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-42.jpg)
где первоначально L = 1, R = n , а в качестве разделителя берется x = a[k]. В результате разделения получаются индексы i, j такие, что
a[h] < x, h < i; a[h] > x, h > j; i > j;
a) если j ≤ k ≤ i, то элемент a[k] разделяет массив на две части в нужной пропорции; алгоритм заканчивает вою работу;
b) если i < k, то выбранное значение х было слишком мало, поэтом процесс разделения необходимо выполнить на отрезке [i, R]
c) если k < j , то значение x было слишком велико, поэтому процесс разделения необходимо выполнить на отрезке [L, j]
2. Процесс разделения повторять до тех пор, пока не возникнет ситуация а) - значение x соответствует значению k-oгo наименьшего элемента.
Слайд 44Реализация (A1)
L ← 1; R ← n;
while (L< k) {
x ←A[k];
Разделение
![Реализация (A1) L ← 1; R ← n; while (L x ←A[k];](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-43.jpg)
a[L] … a[R]
if (i < k) {L ← i;}
if (k < j) {R ← j;}
if (j ≤ k ≤ i) {return x ; break;}
}
Слайд 45Оценка сложности алгоритма (A1)
Если предположить, что разделение в среднем разбивает часть, где
![Оценка сложности алгоритма (A1) Если предположить, что разделение в среднем разбивает часть,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-44.jpg)
находится требуем элемент пополам, то рекуррентное уравнение будет иметь вид T(n) = Cn + T(n/2)
По теореме о решении рекуррентного уравнения трудоемкость алгоритма в среднем есть Θ(n).
Таким образом, получаем явное преимущество по сравнению с прямыми методами, где сначала сортируется все множество, а затем выбирается k-ый элемент.
В худшем случае, когда в качестве разделителя берется максимальный (минимальный элемент) рассматриваемой подпоследовательности, рекуррентное уравнение будет иметь вид
T(n) = Cn + T(n - 1)
трудоемкость алгоритма в этом случае Θ(n2)
Слайд 46Выбор элемента с k номером (A2)
Разбиваем исходную последовательность А на n/5 подпоследовательностей
![Выбор элемента с k номером (A2) Разбиваем исходную последовательность А на n/5](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-45.jpg)
по пять элементов в каждой. В каждой такой подпоследовательности находим медиану. Это потребует C1n операций.
Из найденных на первом шаге медиан строим последовательность M и рекурсивно находим ее медиану x. Так как длина рассматриваемой последовательности M равна n/5, то трудоемкость нахождения медианы для этой последовательности равна T (n/5).
Для полученного элемента x выполним процесс разделения, который потребует C2n операций. В результате вся рассматриваемая последовательность А будет разбита на части: А1 , где элементы не больше x; А2 , где элемент не меньше x. Одна из частей может быть отброшена, причем не сложно показать, что количество элементов каждой из частей не меньше n/4.
Решаем задачу нахождения k-oгo наименьшего элемента оставшихся 3n/4 элементов, что потребует времени T(3n/4).
Слайд 47Оценка сложности алгоритма (A2)
Таким образом, рекуррентное уравнение для описанного выше алгоритма имеет
![Оценка сложности алгоритма (A2) Таким образом, рекуррентное уравнение для описанного выше алгоритма](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-46.jpg)
вид
T(n) = C1n + T(n/5) + C2n + T(3n/4)
Решая данное уравнение методом подстановки, при g(n) = 20Cn или методом рекурсивны деревьев, получаем, что трудоемкость приведенного выше алгоритма есть Θ(n).
Если исходную последовательность разбивать на семерки, то рекуррентное уравнение будет иметь вид
T(n) = C3n + T(n/7)+T(3n/4)<(28/3)C3n
Слайд 48Сортировка вычерпыванием
Алгоритм сортировки вычёрпыванием (bucket sort) работает за линейное (среднее) время. Эта
![Сортировка вычерпыванием Алгоритм сортировки вычёрпыванием (bucket sort) работает за линейное (среднее) время.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-47.jpg)
сортировка годится не для любых исходных данных: говоря о линейном среднем времени, мы предполагаем, что на вход подаётся последовательность независимых случайных чисел, равномерно распределённых на промежутке [0; 1).
Заметим, что этот алгоритм – детерминированный (не использует генератора случайных чисел); понятие случайности возникает лишь при анализе времени его работы.
Слайд 49Сортировка вычерпыванием
промежуток [0; 1) делится на n равных частей, после чего для
![Сортировка вычерпыванием промежуток [0; 1) делится на n равных частей, после чего](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-48.jpg)
чисел из каждой части выделяется свой ящик-черпак (bucket), и n подлежащих сортировке чисел раскладываются по этим ящикам.
Поскольку числа равномерно распределены на отрезке [0;1), следует ожидать, что в каждом ящике их будет немного.
Теперь отсортируем числа в каждом ящике по отдельности и пройдёмся по ящикам в порядке возрастания, выписывая попавшие в каждый из них числа также в порядке возрастания.
Будем считать, что на вход подается n-элементный массив А, причем 0 ≤ А[i] < 1 для всех i.
Используется также вспомогательный массив В[0. .n - 1], состоящий из списков, соответствующих ящикам.
Слайд 50Алгоритм
Алгоритм bucket_sort(A)
n ← length[A]
for i ← 1 to n
{
![Алгоритм Алгоритм bucket_sort(A) n ← length[A] for i ← 1 to n](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-49.jpg)
добавить A[i] к списку B[[nA[i]]] }
for i ← 0 to n-1
{отсортировать список B[i] сортировкой вставками} соединить списки В[0], В[1], …В[n - 1]
Слайд 52Время работы алгоритма
Операции во всех строках, кроме пятой, требуют (общего) времени Θ(n).
![Время работы алгоритма Операции во всех строках, кроме пятой, требуют (общего) времени](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-51.jpg)
Просмотр всех ящиков также занимает время Θ(n). Таким образом, нам остаётся только оценить время сортировки вставками внутри ящиков.
Пусть в ящик B[i] попало ni чисел (ni – случайная величина).
Поскольку сортировка вставками работает за квадратичное время, MO длительности сортировки чисел в ящике номер i есть Θ(М[ni2 ]), а MO суммарного времени сортировки по всех ящиках есть О(n)
Т.е. МО времени работы алгоритма сортировки вычёрпыванием в самом деле линейно зависит от количества чисел.
Слайд 53Время работы алгоритма
Т.к. числа распределены равномерно, а величины всех отрезков равны, вероятность
![Время работы алгоритма Т.к. числа распределены равномерно, а величины всех отрезков равны,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-52.jpg)
того, что данное число попадет в ящик номер n, равна 1/n.
Это аналогично примеру с шарами и урнами: у нас n шаров-чисел, n урн-ящиков, и вероятность попадания данного шара в данную урну равна р=1/n.
Поэтому числа ni распределены биномиально:
P( ni = k)= Сnkрk (1 – p)n–k ,
М[ni]=nр=1, и
D[ni] = nр(1–р) = 1–1/n.
Слайд 54Лексикографическая сортировка
Пусть S некоторое множество на котором задан
‹– линейный порядок.
Лексикографическим
![Лексикографическая сортировка Пусть S некоторое множество на котором задан ‹– линейный порядок.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-53.jpg)
порядком на множестве S называется такое продолжение отношения ‹ на кортежи (списки, слова) элементов из S при котором
(s1 , s2 , …, sp ) ‹ (t1 , t2 , …, tq )
означает выполнение одного из условий:
существует целое j, что sj ‹ tj и для всех i < j справедливо si = ti .
p ≤ q и si = ti при 1 ≤ i ≤ p.
Слайд 55Лексикографическая сортировка
Очевидно, что любое целое число можно считать k-членным кортежем цифр от
![Лексикографическая сортировка Очевидно, что любое целое число можно считать k-членным кортежем цифр](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-54.jpg)
0 до n – 1, где n - основание системы счисления, в которой рассматриваются цифры.
Рассмотрим сначала сортировку k-членных кортежей, элементы которых заключены в интервале от ‘a’ до ‘z’.
Слайд 56Сортировка вычёрпыванием
Создадим исходную очередь A из n элементов, в которую занесем все
![Сортировка вычёрпыванием Создадим исходную очередь A из n элементов, в которую занесем](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-55.jpg)
рассматриваемые кортежи длины k.
Организуем количество очередей, равное количеству маленьких латинских букв в алфавите. Для этого используем вспомогательный массив В[‘a’..’z’], состоящий из списков, соответствующих ящикам-черпакам.
Количество итераций равно длине кортежей.
на i -ой итерации идет сортировка по k–i + 1 компоненте кортежей, т.е. некоторый кортеж А[j] удаляется из исходной очереди и добавляется в очередь В[А[j][k–i + 1]].
после выполнения i-ой итерации, в исходной очереди находится последовательность кортежей, полученная в результате “переписывания” (удаления и добавления) элементов всех непустых очередей, начиная с очереди, адрес начала которой находится в переменной В[‘a’], и заканчивая – B[‘z’].
Слайд 57Рекуррентное уравнение для алгоритма
Пусть m — количество организованных очередей, тогда трудоемкость сортировки
![Рекуррентное уравнение для алгоритма Пусть m — количество организованных очередей, тогда трудоемкость](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-56.jpg)
кортежей по некоторой компоненте есть Θ(n+m),
т.к. количество кортежей – n и их можно распределить по очередям за время O(n); для сцепления m очередей требуется время O(m).
Тогда рекуррентное уравнение будет иметь вид:
T(k) = (n + m) + T(k – 1), T(k) = Θ(k (n + m)).
Слайд 58Алгоритм
Алгоритм lexicographical_sort
k ← length(A[1]);
for c ← ‘a’ to ‘z’
{
![Алгоритм Алгоритм lexicographical_sort k ← length(A[1]); for c ← ‘a’ to ‘z’](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-57.jpg)
B[c].tail ← null; B[c].head ← null; }
for i ← 1 to k {
for j ← 1 to n { B[A[j][k – i + 1]].moveToQueue(A[j]); }
s ← 1;
for c ← ‘a’ to ‘z’
while B[c].head ≠ null
{ A[s] ← B[c].removeFromQueue; s++; }
}
Слайд 59Алгоритм сортировки кортежей разной длины
Сначала сортируемые кортежи располагаются в порядке убывания
![Алгоритм сортировки кортежей разной длины Сначала сортируемые кортежи располагаются в порядке убывания](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-58.jpg)
длины.
Пусть lтах - длина самого длинного кортежа, тогда сортировка вычёрпыванием производится lтах раз.
На начальном этапе в исходную очередь А для сортировки помещаются только кортежи длины lтах и на первом этапе для сортировки используется только компонента lтах .
После этого в исходную очередь А добавляются все кортежи длины lтах – 1, и для сортировки используется только компонента lтах – 1.
На следующих этапах происходит сортировка соответствующей компоненты lтах – 2, … 1, аналогичным образом.
Слайд 60Алгоритм сортировки кортежей разной длины
![Алгоритм сортировки кортежей разной длины](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-59.jpg)
Слайд 62Пример
Дан массив:
Один, Два, Три, Четыре, Пять, Шесть, Семь, Восемь, Девять, Десять
Упорядочиваем по
![Пример Дан массив: Один, Два, Три, Четыре, Пять, Шесть, Семь, Восемь, Девять,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-61.jpg)
длине:
6 – Четыре, Восемь, Девять, Десять
5 – Шесть
4 – Один, Пять, Семь
3 – Два, Три
Слайд 631-я итерация
Вспомогательный массив B:
e: Четыре
Ь: Восемь, Девять, Десять
![1-я итерация Вспомогательный массив B: e: Четыре Ь: Восемь, Девять, Десять](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-62.jpg)
Слайд 642-я итерация
Вспомогательный массив B:
м: Восемь
р: Четыре
т: Девять, Десять
ь: Шесть
![2-я итерация Вспомогательный массив B: м: Восемь р: Четыре т: Девять, Десять ь: Шесть](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-63.jpg)
Слайд 653-я итерация
Вспомогательный массив B:
е: Восемь
н: Один
т: Шесть
ь: Пять, Семь
ы: Четыре
я: Девять,
![3-я итерация Вспомогательный массив B: е: Восемь н: Один т: Шесть ь:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-64.jpg)
Десять
Слайд 664-я итерация
Вспомогательный массив B:
а: Два
в: Девять
и: Один, Три
м: Семь
с: Восемь, Шесть,
![4-я итерация Вспомогательный массив B: а: Два в: Девять и: Один, Три](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-65.jpg)
Десять
т: Пять, Четыре
Слайд 675-я итерация
Вспомогательный массив B:
в: Два
д: Один
е: Девять, Семь, Шесть, Десять, Четыре
![5-я итерация Вспомогательный массив B: в: Два д: Один е: Девять, Семь,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-66.jpg)
о: Восемь
р: Три
я: Пять
Слайд 686-я итерация
Вспомогательный массив B:
в: Восемь
д: Два, Девять, Десять
о: Один
п: Пять
с: Семь
т: Три
ч:
![6-я итерация Вспомогательный массив B: в: Восемь д: Два, Девять, Десять о:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-67.jpg)
Четыре
ш: Шесть
Слайд 69Пирамидальная сортировка
Сортировка пирамидой использует бинарное сортирующее дерево.
Сортирующее дерево — это такое дерево,
![Пирамидальная сортировка Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-68.jpg)
у которого выполнены условия:
Каждый лист имеет глубину либо d либо d−1, d — максимальная глубина дерева.
Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.
Слайд 70Пирамидальная сортировка
Этап 1. Выстраиваем элементы массива в виде сортирующего дерева
A[i] ≥ A[2i+1]
![Пирамидальная сортировка Этап 1. Выстраиваем элементы массива в виде сортирующего дерева A[i]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-69.jpg)
A[i] ≥ A[2i+2]
0 ≤ i < [n/2]
Этот шаг требует O(n) операций.
Слайд 71Пирамидальная сортировка
Этап 2. Будем удалять элементы из корня по одному за раз
![Пирамидальная сортировка Этап 2. Будем удалять элементы из корня по одному за](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-70.jpg)
и перестраивать дерево, т.е. обменивать A[0] и A[n-1]. В результате обмена A[n-1] будет хранить максимальный элемент массива. Далее уменьшаем размер массива на 1(исключаем последний элемент) и переходим к этапу 1.
Продолжаем до тех пор, пока в дереве не останется 1 элемент.
Этот шаг требует O(nlogn) операций.
Слайд 72Достоинства сортировки
Имеет доказанную оценку худшего случая O(nlogn).
Сортирует на месте, то есть требует
![Достоинства сортировки Имеет доказанную оценку худшего случая O(nlogn). Сортирует на месте, то](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-71.jpg)
всего O(1) дополнительной памяти.
Слайд 73Недостатки сортировки
Неустойчив — для обеспечения устойчивости нужно расширять ключ.
На почти отсортированных массивах работает
![Недостатки сортировки Неустойчив — для обеспечения устойчивости нужно расширять ключ. На почти](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/993586/slide-72.jpg)
столь же долго, как и на хаотических данных.
Из-за сложности алгоритма выигрыш получается только на больших n.