Теория алгоритмов. Сортировка массива. (Лекция 17)

Сентябрь 6, 2022

Главная
Алгебра
Теория алгоритмов. Сортировка массива. (Лекция 17)

Содержание

2. План План Сортировка: общие замечания Задача сортировки Внутренняя и внешняя сортировка Устойчивость Сортировка массива Сортировка прямыми
3. Сортировка: общие замечания Задача сортировки Внутренняя и внешняя сортировка Устойчивость Сортировка массива
4. Сортировка: общие замечания Сортировка Сортировка – процесс перестановки объектов заданной совокупности в определенном порядке (возрастающем или
5. Сортировка: общие замечания Сортировка: более формально Дано: N объектов a1, a2, …, aN Требуется: упорядочить заданные
6. Сортировка: общие замечания Сортировка: устойчивость При устойчивой сортировке относительный порядок элементов с одинаковыми ключами не меняется
7. Сортировка: общие замечания Сортировка массивов Массив – одна из наиболее распространенных совокупностей, подвергаемых сортировке От алгоритмов
8. Сортировка: общие замечания Сортировка массивов: алгоритмы Простые методы сортировки – прямые, временная сложность – O(n2) сортировка
9. Сортировка прямыми выставками Идея Псевдокод Анализ алгоритма Сортировка бинарными вставками
10. Сортировка вставками Сортировка вставками
11. Сортировка вставками 1 3 4 8 10 14 16 21 24 31 33 36 38 42
12. Сортировка вставками Сортировка простыми вставками
13. Сортировка вставками Сортировка простыми вставками Анализ алгоритма Лучший случай: массив упорядочен Худший случай: массив упорядочен в
14. Сортировка вставками Сортировка бинарными вставками Сортировка простыми вставками может быть улучшена Можно ускорить поиск подходящего места
15. Сортировка прямым выбором Идея Псевдокод Анализ алгоритма
16. Сортировка выбором 1 3 4 8 10 14 16 21 24 31 33 36 38 42
17. Сортировка выбором Сортировка простым выбором SELECTIONSORT(A) 1 for i ← 1 to length[A] – 1 do
18. Сортировка выбором Сортировка простым выбором Анализ алгоритма Количество сравнений не зависит от начального порядка элементов: Лучший
19. Сортировка прямыми обменами Идея Псевдокод Анализ алгоритма
20. Сортировка обменами Сортировка простыми обменами (пузырьковая сортировка) Идея: пузырек воздуха в стакане воды поднимается со дна
21. Сортировка обменами Сортировка простыми обменами (пузырьковая сортировка)
22. Сортировка обменами void main() { const int N = 10; int A[N], i, j, c; //
23. Сортировка обменами Улучшенный метод «пузырька» Если при выполнении очередного прохода не было обменов, то массив уже
24. Сортировка обменами Улучшенный метод «пузырька» i = 0; do { flag = 0; // сбросить флаг
25. Сортировка обменами Шейкерная сортировка Метод пузырька несимметричен При нарушении почти полного порядка «легкими» элементами, требуется мало
26. Сортировка обменами Шейкерная сортировка
27. Сортировка обменами Сортировка простыми обменами Анализ алгоритма Лучший случай: массив упорядочен Худший случай: массив упорядочен в
28. Сортировка обменами «Шейкерная» сортировка Анализ алгоритма Лучший случай: массив упорядочен Худший случай: массив упорядочен в обратном
29. Сортировка обменами Прямые методы сортировки Сортировка обменами несколько менее эффективна сортировок вставками и выбором Шейкерная сортировка
30. Сортировка Шелла Идея алгоритма Анализ алгоритма
31. Сортировка Шелла Сортировка Шелла (Д.Л.Шелл, 1959) Элементы разбиваются на подмножества для некоторого h>1 a1, a1+h, a1+2h,
32. Сортировка Шелла Сортировка Шелла 1 2 3 4 5 6 7 8 9 10 11 12
33. Сортировка Шелла Сортировка Шелла Анализ алгоритма Анализ приводит к сложным математическим задачам Для эффективной сортировки соседние
34. Сортировка слиянием Идея алгоритма Временная сложность алгоритма
35. Сортировка слиянием 1 3 4 8 14 24 31 42 27 51 59 int[] merge(int[] a,
36. Сортировка слиянием 1 3 4 8 10 14 16 21 24 31 33 36 38 42
37. Сортировка слиянием Алгоритм сортировки слиянием (фон Неймана) Псевдокод // Merge() сливает два упорядоченных подмассива // в
38. Сортировка слиянием #include #include void merge (int *a, int n, int m) { int i, j,
39. Сортировка слиянием Сортировка слиянием Анализ алгоритма Анализ приводит к сложным математическим задачам Асимптотическая сложность – O(N
40. Быстрая сортировка Идея алгоритма Временная сложность алгоритма
41. Быстрая сортировка 1 3 4 8 10 14 16 21 24 31 33 36 38 42
42. Быстрая сортировка Быстрая сортировка Псевдокод
43. Пример программы int a[100]; void quickSort(int l, int r) { int x = a[l + (r
44. Быстрая сортировка Улучшения алгоритма Первый элемент в сортируемом куске выбирается случайно и запоминается Участки, меньшие определенного
45. Быстрая сортировка Быстрая сортировка Анализ алгоритма Эффективность во многом зависит от сбалансированности разбиения на подмассивы Наихудшее
47. Скачать презентацию

Слайд 2

План
План
Сортировка: общие замечания
Задача сортировки
Внутренняя и внешняя сортировка
Устойчивость
Сортировка массива
Сортировка прямыми вставками
Идея
Псевдокод
Анализ алгоритма
Сортировка

бинарными вставками
Сортировка прямым выбором
Идея алгоритма
Временная сложность алгоритма
Сортировка прямыми обменами
Идея алгоритма
Временная сложность алгоритма
Улучшения алгоритма
Шейкерная сортировка

Сортировка Шелла
Идея алгоритма
Временная сложность алгоритма
Сортировка слияниями
Идея алгоритма
Временная сложность алгоритма
Быстрая сортировка
Идея алгоритма
Временная сложность алгоритма

Слайд 3

Сортировка: общие замечания
Задача сортировки
Внутренняя и внешняя сортировка
Устойчивость
Сортировка массива

Слайд 4

Сортировка: общие замечания
Сортировка
Сортировка – процесс перестановки объектов заданной совокупности в определенном

порядке (возрастающем или убывающем)
Целью сортировки обычно является облегчение последующего поиска элементов в отсортированном множестве
В зависимости от объема и структуры данных методы сортировки подразделяются на:
Внутренние – сортировка массивов
Внешние – сортировка файлов

Слайд 5

Сортировка: общие замечания
Сортировка: более формально
Дано: N объектов a1, a2, …, aN
Требуется:

упорядочить заданные объекты, т.е. переставить их в такой последовательности ap1, ap2, …, apN, чтобы их ключи расположились в неубывающем порядке kp1 ≤ kp2 ≤ … ≤ kpN
Ключ ki = f(ai) – некоторая функция элемента
ai – целое число => ki = ai
ai – структура => ki = ai.key

Слайд 6

Сортировка: общие замечания
Сортировка: устойчивость
При устойчивой сортировке относительный порядок элементов с одинаковыми

ключами не меняется
Если kpi ≤ kpj и i < j, то pi < pj
Устойчивость желательна, если элементы уже упорядочены

Слайд 7

Сортировка: общие замечания
Сортировка массивов
Массив – одна из наиболее распространенных совокупностей, подвергаемых

сортировке
От алгоритмов сортировки массива требуется
экономичность по памяти
Перестановки, упорядочивающие массив, должны выполняться на том же месте
экономичность по времени
Мера эффективности C – количество сравнений ключей и M – число перестановок элементов

Слайд 8

Сортировка: общие замечания
Сортировка массивов: алгоритмы
Простые методы сортировки – прямые, временная сложность

– O(n2)
сортировка прямыми вставками (by insertion)
сортировка прямым выбором (by selection)
сортировка прямыми обменами выбором (by exchange)
«Улучшенные» методы сортировки, временная сложность – O(n log n)
быстрая сортировка Хоара (quicksort)
сортировка слияниями (mergesort)
coртировка Шелла (shellsort)
…

Слайд 9

Сортировка прямыми выставками
Идея
Псевдокод
Анализ алгоритма
Сортировка бинарными вставками

Слайд 10

Сортировка вставками
Сортировка вставками

Слайд 11

Сортировка вставками
1
3
4
8
10
14
16
21
24
31
33
36
38
42
44
50
53
59
1
3
4
8
10
14
16
21
24
31
33
36
38
42
44
50
27
51
53
59
1
3
4
8
10
14
16
21
24
31
33
36
38
42
44
50
27
51
53
59
1
3
8
10
16
21
24
33
36
38
44
50
53
59
Сортировка простыми вставками
Массив делится на две части
«готовую» a1, a2,

…, ai-1
исходную ai, ai+1, …, aN
Для каждого i от 2 до N
из исходной части извлекается i-й элемент
вставляется в готовую часть на нужное место

Слайд 12

Сортировка вставками
Сортировка простыми вставками

Слайд 13

Сортировка вставками
Сортировка простыми вставками
Анализ алгоритма
Лучший случай: массив упорядочен
Худший случай: массив

упорядочен в обратном порядке
Сmin = N – 1 Mmin = 3(N-1)
Cavg = (N2 + N – 2)/4 Mavg = (N2 + 9N – 10)/4
Cmax = (N2 + N – 4)/2 Mmax = (N2 + 3N – 4)/2
Итог: T(N) = C(N) + M(N) = O(N2)

Слайд 14

Сортировка вставками
Сортировка бинарными вставками
Сортировка простыми вставками может быть улучшена
Можно ускорить

поиск подходящего места в «готовой» части, т.к. она упорядочена
В упорядоченной последовательности применим бинарный поиск!
Сложность бинарного поиска в худшем случае есть O(log N)
Количество сравнений есть O(N log N)
Но по-прежнему, M(N) = O(N2)
Итог: T(N) = O(N log N) +O(N2) = O(N2)

Слайд 15

Сортировка прямым выбором
Идея
Псевдокод
Анализ алгоритма

Слайд 16

Сортировка выбором
1
3
4
8
10
14
16
21
24
31
33
36
38
42
44
50
53
59
Сортировка простым выбором
Массив делится на две части
«готовую» a1, a2,

…, ai-1
исходную ai, ai+1, …, aN
Для каждого i от 1 до N–1
присвоить k индекс минимального элемента в исходной части
поменять местами элементы ai и ak

Слайд 17

Сортировка выбором
Сортировка простым выбором
SELECTIONSORT(A)
1 for i ← 1 to length[A] –

1 do
2 k ← i
3 x ← A[i]
4 for j ← 1 to length[A] – 1 do
5 if A[j] < x then
6 k ← j
7 x ← A[j]
8 A[k] ← A[i]
9 A[i] ← x

Слайд 18

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

элементов:
Лучший случай: массив упорядочен
Худший случай: массив упорядочен в обратном порядке
С = (N2 – N)/2 Mmin = 3(N – 1)
Mavg ≈ N(ln N + γ), γ = 0.577216…
Mmax = ⎣N2/4⎦ + 3(N – 1)
Итог (худший случай) : T(N) = C(N) + M(N) = O(N2)
В среднем сортировка выбором выгоднее сортировки вставками

Слайд 19

Сортировка прямыми обменами
Идея
Псевдокод
Анализ алгоритма

Слайд 20

Сортировка обменами
Сортировка простыми обменами (пузырьковая сортировка)
Идея: пузырек воздуха в стакане воды поднимается

со дна вверх – самый маленький («легкий») элемент массива перемещается вверх («всплывает»)
Для каждого i от 2 до N
Для каждого j от N до i
Если в паре элементов aj –1 и aj нарушен порядок,
то поменять местами aj –1 и aj

1-ый проход

2-ой проход

3-ий проход

Слайд 21

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

Слайд 22

Сортировка обменами
void main() {
const int N = 10;
int A[N],

i, j, c;
// заполнить массив
// вывести исходный массив
for (i = 0; i < N-1; i ++){
for (j = N-2; j >= i ; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
}
}
// вывести полученный массив
}

элементы выше A[i] уже поставлены

меняем A[j] и A[j+1]

Си-программа

Слайд 23

Сортировка обменами
Улучшенный метод «пузырька»
Если при выполнении очередного прохода не было обменов,

то массив уже отсортирован и остальные проходы не нужны
Реализуется через переменную-флаг, показывающую, были ли обмены
Если флаг поднят, то обмены были и нужен еще один проход
Если флаг опущен, то – выход

Слайд 24

Сортировка обменами
Улучшенный метод «пузырька»
i = 0;
do {
flag = 0; //

сбросить флаг
for ( j = N-2; j >= i ; j -- )
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = 1; // поднять флаг
}
i ++;
}
while ( flag ); // выход при flag = 0

i ++;

Слайд 25

Сортировка обменами
Шейкерная сортировка
Метод пузырька несимметричен
При нарушении почти полного порядка «легкими» элементами,

требуется мало проходов
При нарушении почти полного порядка «тяжелыми» элементами, требуется много проходов
Выход: чередовать направления проходов

1 проход

3 прохода

Слайд 26

Сортировка обменами
Шейкерная сортировка

Слайд 27

Сортировка обменами
Сортировка простыми обменами
Анализ алгоритма
Лучший случай: массив упорядочен
Худший случай: массив упорядочен

в обратном порядке
Сmin = (N2 – N)/2 Mmin = 0
Cavg = (N2 – N)/2 Mavg = (N2 – N)/4
Cmax = (N2 – N)/2 Mmax = (N2 – N)/2
Итог: T(N) = C(N) + M(N) = O(N2)

Слайд 28

Сортировка обменами
«Шейкерная» сортировка
Анализ алгоритма
Лучший случай: массив упорядочен
Худший случай: массив упорядочен в

обратном порядке
Сmin = N – 1 Mmin = 0
Cavg = (N2 – N(k+ln N))/2 Mavg = (N2 – N)/4
Cmax = (N2 – N)/2 Mmax = (N2 – N)/2
Итог: T(N) = C(N) + M(N) = O(N2)

Слайд 29

Сортировка обменами
Прямые методы сортировки
Сортировка обменами несколько менее эффективна сортировок вставками и

выбором
Шейкерная сортировка выгодна, когда массив почти упорядочен
Общее свойство: перемещение элементов ровно на одну позицию за один прием
Можно показать, что среднее расстояние, на которое должен сдвигаться элемент равно N/3
Надо стремиться к дальним пересылкам элементов

Слайд 30

Сортировка Шелла
Идея алгоритма
Анализ алгоритма

Слайд 31

Сортировка Шелла
Сортировка Шелла (Д.Л.Шелл, 1959)
Элементы разбиваются на подмножества для некоторого h>1
a1,

a1+h, a1+2h, a1+3h,…
a2, a2+h, a2+2h, a2+3h,…
…
at, at+h, at+2h, at+3h,…
Сортировка проводится методом вставок для каждого подмножества
h уменьшается и процедура повторяется, пока h>0

Слайд 32

Сортировка Шелла
Сортировка Шелла
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
0
step=7
1
3
4
8
10
14
16
21
24
31
33
36
38
42
44
50
27
51
53
59
step=3
step=2
step=1

Слайд 33

Сортировка Шелла
Сортировка Шелла
Анализ алгоритма
Анализ приводит к сложным математическим задачам
Для эффективной сортировки

соседние значения не должны быть кратными
Иначе массив распадается на непересекающиеся цепочки
Требуется, чтобы цепочки взаимодействовали как можно чаще
Д. Кнут предлагает выбирать h так (порядок обратный):
1, 4, 13, 40, 121, …, т.е. hk–1 = 3hk+1, ht=1, t = [log3N] – 1
1, 3, 7, 15, 31, …, т.е. hk–1 = 2hk+1, ht=1, t = [log2N] – 1

Количество перестановок элементов M (по результатам экспериментов со случайными массивами)

Слайд 34

Сортировка слиянием
Идея алгоритма
Временная сложность алгоритма

Слайд 35

Сортировка слиянием
1
3
4
8
14
24
31
42
27
51
59
int[] merge(int[] a, int[] b) {
int na = a.length,

nb = b.length,
nc;
int[] c = new int[nc = na + nb];
int ia = 0,
ib = 0,
ic = 0;
while (ia < na && ib < nb) {
if (a[ia] < b[ib])
c[ic++] = a[ia++];
else
c[ic++] = b[ib++];
}
while (ia < na) c[ic++] = a[ia++];
while (ib < nb) c[ic++] = b[ib++];
return c;
}

Cлияние упорядоченных массивов

Java-код

Слайд 36

Сортировка слиянием
1
3
4
8
10
14
16
21
24
31
33
36
38
42
44
50
27
51
53
59
И так далее…
Сортировка слиянием (фон Неймана)

Слайд 37

Сортировка слиянием
Алгоритм сортировки слиянием (фон Неймана)
Псевдокод
// Merge() сливает два упорядоченных подмассива
//

в единый подмассив
MergeSort(A, left, right) {
if (left < right) {
mid = floor((left + right) / 2); // середина
MergeSort(A, left, mid);
MergeSort(A, mid+1, right);
Merge(A, left, mid, right);
}
}

Слайд 38

Сортировка слиянием
#include #include void merge (int *a, int n, int m)

{ int i, j, k; int *x = malloc(n * sizeof (int)); for (i = 0, j = m, k = 0; k < n; k++)
{ x[k] = j == n ? a[i++]: i == m ? a[j++]: a[j] < a[i] ?a[j++]: a[i++]; } for (i = 0; i < n; i++) { a[i] = x[i]; } free(x);
}

Алгоритм сортировки слиянием (фон Неймана)

void merge_sort (int *a, int n) { if (n < 2) return; int m = n / 2; merge_sort(a, m); merge_sort(a + m, n - m); merge(a, n, m); } int main () { int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; int n = sizeof a / sizeof a[0]; int i; for (i = 0; i < n; i++) printf("%d%s", a[i], i == n - 1 ? "\n" : " "); merge_sort(a, n); for (i = 0; i < n; i++) printf("%d%s", a[i], i == n - 1 ? "\n" : " "); return 0; }

Output:
4 65 2 -31 0 99 2 83 782 1
-31 0 1 2 2 4 65 83 99 782

Слайд 39

Сортировка слиянием
Сортировка слиянием
Анализ алгоритма
Анализ приводит к сложным математическим задачам
Асимптотическая сложность –

O(N log N)

Слайд 40

Быстрая сортировка
Идея алгоритма
Временная сложность алгоритма

Слайд 41

Быстрая сортировка
1
3
4
8
10
14
16
21
24
31
33
36
38
42
44
50
27
51
53
59
Быстрая сортировка (Хоара)

Слайд 42

Быстрая сортировка
Быстрая сортировка
Псевдокод

Слайд 43

Пример программы
int a[100]; void quickSort(int l, int r) { int x = a[l + (r - l) / 2]; //запись эквивалентна (l+r)/2, //но не вызввает переполнения на

больших данных int i = l; int j = r; //код в while обычно выносят в процедуру particle while(i <= j) { while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j) { swap(a[i], a[j]); i++; j--; } } if (i

Организация курса

int main() { int n;//количество элементов в массиве scanf(“%d”,n]); for(int i = 0; i < n; i++) { scanf(“%d”,a[i]); } quickSort(0, n-1); for(int i = 0; i < n; i++) { printf(“%d ”,a[i]); } return 0; }

Слайд 44

Быстрая сортировка
Улучшения алгоритма
Первый элемент в сортируемом куске выбирается случайно и запоминается
Участки,

меньшие определенного размера, сортируются простыми способами
Иногда исключение рекурсивных вызовов приводит к повышению эффективности

Слайд 45

Быстрая сортировка
Быстрая сортировка
Анализ алгоритма
Эффективность во многом зависит от сбалансированности разбиения на

подмассивы
Наихудшее разбиение: 1 к (N–1) => O(N2)
Лучшее разбиение: N/2 к N/2 => O(N log N)
Средний случай: O(N log N)

Теория алгоритмов. Сортировка массива. (Лекция 17)

Содержание

Сортировка: общие замечанияЗадача сортировкиВнутренняя и внешняя сортировкаУстойчивостьСортировка массива

Сортировка: общие замечанияСортировкаСортировка – процесс перестановки объектов заданной совокупности в определенном

Сортировка: общие замечанияСортировка: более формальноДано: N объектов a1, a2, …, aNТребуется:

Сортировка: общие замечанияСортировка: устойчивостьПри устойчивой сортировке относительный порядок элементов с одинаковыми

Сортировка: общие замечанияСортировка массивовМассив – одна из наиболее распространенных совокупностей, подвергаемых

Сортировка: общие замечанияСортировка массивов: алгоритмыПростые методы сортировки – прямые, временная сложность

Сортировка прямыми выставкамиИдеяПсевдокодАнализ алгоритмаСортировка бинарными вставками

Сортировка вставкамиСортировка вставками

Сортировка вставкамиСортировка простыми вставками

Сортировка вставкамиСортировка простыми вставками Анализ алгоритмаЛучший случай: массив упорядоченХудший случай: массив

Сортировка вставкамиСортировка бинарными вставками Сортировка простыми вставками может быть улучшенаМожно ускорить

Сортировка прямым выборомИдеяПсевдокодАнализ алгоритма

Сортировка выбором13481014162124313336384244505359Сортировка простым выбором Массив делится на две части«готовую» a1, a2,

Сортировка выборомСортировка простым выбором SELECTIONSORT(A)1 for i ← 1 to length[A] –

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

Сортировка прямыми обменамиИдеяПсевдокодАнализ алгоритма

Сортировка обменамиСортировка простыми обменами (пузырьковая сортировка)Идея: пузырек воздуха в стакане воды поднимается

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

Сортировка обменамиvoid main() { const int N = 10; int A[N],

Сортировка обменамиУлучшенный метод «пузырька»Если при выполнении очередного прохода не было обменов,

Сортировка обменамиУлучшенный метод «пузырька»i = 0;do { flag = 0; //

Сортировка обменамиШейкерная сортировкаМетод пузырька несимметриченПри нарушении почти полного порядка «легкими» элементами,

Сортировка обменамиШейкерная сортировка

Сортировка обменамиСортировка простыми обменамиАнализ алгоритмаЛучший случай: массив упорядоченХудший случай: массив упорядочен

Сортировка обменами«Шейкерная» сортировкаАнализ алгоритмаЛучший случай: массив упорядоченХудший случай: массив упорядочен в

Сортировка обменамиПрямые методы сортировкиСортировка обменами несколько менее эффективна сортировок вставками и

Сортировка ШеллаИдея алгоритмаАнализ алгоритма

Сортировка ШеллаСортировка Шелла (Д.Л.Шелл, 1959)Элементы разбиваются на подмножества для некоторого h>1a1,

Сортировка ШеллаСортировка Шелла123456789101112131415161718190step=7134810141621243133363842445027515359step=3step=2step=1

Сортировка ШеллаСортировка ШеллаАнализ алгоритмаАнализ приводит к сложным математическим задачамДля эффективной сортировки

Сортировка слияниемИдея алгоритмаВременная сложность алгоритма

Сортировка слиянием134814243142275159int[] merge(int[] a, int[] b) { int na = a.length,

Сортировка слиянием134810141621243133363842445027515359И так далее…Сортировка слиянием (фон Неймана)

Сортировка слияниемАлгоритм сортировки слиянием (фон Неймана) Псевдокод// Merge() сливает два упорядоченных подмассива//

Сортировка слиянием#include #include void merge (int *a, int n, int m)

Сортировка слияниемСортировка слияниемАнализ алгоритмаАнализ приводит к сложным математическим задачамАсимптотическая сложность –

Быстрая сортировкаИдея алгоритмаВременная сложность алгоритма

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

Быстрая сортировкаБыстрая сортировкаПсевдокод

Пример программыint a[100]; void quickSort(int l, int r) { int x = a[l + (r - l) / 2]; //запись эквивалентна (l+r)/2, //но не вызввает переполнения на

Быстрая сортировкаУлучшения алгоритмаПервый элемент в сортируемом куске выбирается случайно и запоминаетсяУчастки,

Быстрая сортировкаБыстрая сортировкаАнализ алгоритмаЭффективность во многом зависит от сбалансированности разбиения на

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