Методы улучшения алгоритмов сортировок. Лекция 7

Июль 24, 2022

Главная
Информатика
Методы улучшения алгоритмов сортировок. Лекция 7

Содержание

2. Алгоритм сортировки АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ ОБЫЧНО ПО ВОЗРАСТАНИЮ ИЛИ УБЫВАНИЮ
3. Классификация алгоритмов сортировок Методы внутренней сортировки
4. Анализ элементарных алгоритмов сортировок
5. Сортировка Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора метод прямой
6. 55 12 42 94 18 67 44 6 нет да да да да да да 55
7. Методы улучшения сортировки обменом Запомнить, производился ли на данном проходе какой-либо обмен! Если нет – алгоритм
8. Методы улучшения сортировки обменом Ввести логическую переменную – признак наличия хотя бы одного обмена в проходе
9. Методы улучшения сортировки обменом 1+2
10. Методы улучшения сортировки обменом Можно менять направление следующих один за другим проходов - шейкер-сортировка 3
11. Блок-схема шейкер-сортировки Методы улучшения сортировки обменом Параметры блок-схемы сортируемая последовательность {a[i]} индекс ее первого элемента –
12. Методы улучшения сортировки обменом В лучшем случае, когда массив уже упорядочен, потребуется всего один проход и
13. Быстрая сортировка «Разделяй и властвуй" В 1962 году Ч.А.Р. Хоар (Charles Antony Richard Hoare) предложил улучшенный
14. Быстрая сортировка «Разделяй и властвуй" СУТЬ СОРТИРОВКИ: Меняем найденные элементы местами В случае, если не найден
15. Быстрая сортировка «Разделяй и властвуй" 1. Выберем один из элементов массива - барьер 2. Элементы массива
16. Пусть a =42 ― барьерный элемент j ― индекс элемента при проходе налево: j=N, N-1, N-2,
17. 8>7 переносим в правую часть, т. к. 16>7 не переносим, 4 12>7 переносим в правую часть,
18. Быстрая сортировка «Разделяй и властвуй" Блок-схема алгоритма быстрой сортировки Параметры блок-схемы сортируемая последовательность {a[i]} индекс ее
19. Быстрая сортировка «Разделяй и властвуй" Блок-схема процедуры разделения массива Параметры блок-схемы сортируемая последовательность {a[i]} индекс ее
20. Быстрая сортировка «Разделяй и властвуй" Довольно сложный анализ эффективности алгоритма быстрой сортировки Ч. Хоара показал: в
21. Быстрая сортировка «Разделяй и властвуй" Медианой массива (медианным элементом) считается такой его элемент, который не меньше
22. Быстрая сортировка «Разделяй и властвуй" Выбирать медианный элемент довольно сложно, во всяком случае такой выбор представляет
23. Быстрая сортировка «Разделяй и властвуй"
24. Быстрая сортировка «Разделяй и властвуй"
25. Быстрая сортировка
26. Быстрая сортировка «Разделяй и властвуй"
27. Улучшение сортировки вставками Исходное положение: x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] 43 55 12
28. Улучшение сортировки вставками 3 шаг 55 12 42 94 18 67 44 6 12 55 42
29. Улучшение сортировки вставками Алгоритм сортировки вставками можно слегка улучшить На каждом шаге внутреннего цикла проверяются 2
30. Улучшение сортировки вставками Отсортированный массив будет не полон, так как из него исчезло первое число Для
31. Улучшение сортировки вставками Функция GetMin( ) - возвращает элемент, заведомо меньший всех возможных элементов массива, определяется
32. Сортировка методом Шелла Сортировка включениями с уменьшающимся расстоянием Сортировка Шелла была названа в честь ее изобретателя
33. Сортировка методом Шелла Сортировка включениями с уменьшающимся расстоянием Д. Шелл предложил выполнить несколько таких проходов с
34. Сортировка методом Шелла Пример 1
35. Сортировка методом Шелла Пример 2
36. Сортировка методом Шелла Пример 3 12 8 14 6 4 1 2 3 4 1 2
37. Сортировка методом Шелла Пример 3 4 1 6 3 шаг. 1 группа из 8-ми элементов Массив
38. Сортировка методом Шелла Блок-схема алгоритма сортировки Шелла с выбором шагов, предложенных Кнутом: …, 121, 40, 13,
39. Сортировка методом Шелла
40. Сортировка методом Шелла
41. Эффективность изученных алгоритмов сортировка вставками со сторожевым элементом
42. По результатам замеров производительности методов можно сделать следующие выводы: Наиболее универсальным методом, является метод быстрой сортировки
43. По результатам замеров производительности методов можно сделать следующие выводы: При использовании небольших массивов данных нет большой
44. вставка выбор обмен метод Шелла Эффективность изученных алгоритмов
46. Скачать презентацию

Слайд 2

Алгоритм сортировки
АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ ОБЫЧНО ПО ВОЗРАСТАНИЮ

ИЛИ УБЫВАНИЮ

Слайд 3

Классификация алгоритмов сортировок
Методы внутренней сортировки

Слайд 4

Анализ элементарных алгоритмов сортировок

Слайд 5

Сортировка
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
метод прямой

вставки
сложные, но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка

сложность O(N2)

сложность O(N·logN)

НЕ СУЩЕСТВУЕТ УНИВЕРСАЛЬНОГО, НАИБОЛЕЕ ЭФФЕКТИВНОГО СПОСОБА СОРТИРОВКИ

Слайд 6

55
12
42
94
18
67
44
6
нет
да
да
да
да
да
да
55
12
42
94
18
67
44
6
нет
да
да
нет
да
да
55
12
42
94
18
67
44
6
55
12
42
94
18
67
44
6
Сортировка обменом / метод пузырька

Слайд 7

Методы улучшения сортировки обменом
Запомнить, производился ли
на данном проходе какой-либо обмен!
Если

нет – алгоритм заканчивает работу

Слайд 8

Методы улучшения сортировки обменом
Ввести логическую переменную – признак наличия хотя бы

одного обмена в проходе

Слайд 9

Методы улучшения сортировки обменом
1+2

Слайд 10

Методы улучшения сортировки обменом
Можно менять направление следующих один за другим проходов

- шейкер-сортировка

Слайд 11

Блок-схема
шейкер-сортировки
Методы улучшения сортировки обменом
Параметры блок-схемы
сортируемая последовательность {a[i]}
индекс ее первого элемента –

lb (lower bound - нижняя граница)
индекс ее последнего элемента - ub (upper bound - верхняя граница)

Слайд 12

Методы улучшения сортировки обменом
В лучшем случае, когда массив уже упорядочен, потребуется

всего один проход и n-1 сравнение, что составляет O(n). Перестановки в этом случае не выполняются
В худшем случае эти виды улучшенной сортировки
не отличаются от исходного алгоритма

Слайд 13

Быстрая сортировка «Разделяй и властвуй"
В 1962 году Ч.А.Р. Хоар (Charles Antony

Richard Hoare) предложил улучшенный вариант обменной сортировки
Основная идея улучшения - обменивать не рядом стоящие элементы массива, а расположенные как можно дальше
друг от друга
СУТЬ СОРТИРОВКИ:
Выбирается некоторое значение (x)- барьерный элемент;
Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x
Затем просматриваем его справа налево, пока не найдется элемент, меньший x

Слайд 14

Быстрая сортировка «Разделяй и властвуй"
СУТЬ СОРТИРОВКИ:
Меняем найденные элементы местами
В случае, если

не найден наибольший или наименьший элементы, местами меняется средний элемент с найденным наибольшим или наименьшим элементом;
Дойдя до середины имеем 2 части массива;
Процесс продолжается для каждой части, пока массив не будет отсортирован

Слайд 15

Быстрая сортировка «Разделяй и властвуй"
1. Выберем один из элементов массива -

барьер

2. Элементы массива просматриваем с двух концов. При просмотре слева направо (начиная с первого) выбираем элемент, не меньший чем барьерный. А во время просмотра справа налево (начиная с последнего) выбирается элемент не больший чем барьерный
3. Найденная пара элементов меняется местами, после чего просмотры возобновляются
4. Завершается проход по массиву после того, как индекс просмотра слева, станет больше чем индекс просмотра справа

барьер

Проход направо

Проход налево

ПРИМЕР:

Слайд 16

Пусть a =42 ― барьерный элемент
j ― индекс элемента

при проходе налево: j=N, N-1, N-2, …

i ― индекс элементов при проходе направо: i=1, 2, …

Проход слева направо: i=1, x1 (=44) > a (=42).

Проход справа налево: j=7, x7 (=6) < a (=42).

Обмен

Проход слева направо: i=2, x2 (=55) > a (=42).

Проход справа налево: j=6, x6 (=18) < a (=42).

Проход слева направо: i=4, Достигнут барьер

Проход справа налево: j=4, Достигнут барьер

Меньше барьерного

Больше барьерного

Как следует поступить далее?

Можно рекурсивно отсортировать обе части массива

Слайд 17

8>7 переносим в правую часть, т. к.
16>7 не переносим, 4<7

поэтому меняем местами 4 и 8

12>7 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим,
7=7 поэтому меняем местами 7 и 12

12>11 переносим в правую часть, т. к.
16>11 не переносим, 8<11 поэтому меняем местами 12 и 8

19>11 переносим в правую часть, т. к. 16>11, 12>11,не переносим,
11=11 поэтому меняем местами 11 и 19

19>12 переносим в правую часть, т. к. 16>12,не переносим,
12=12 поэтому меняем местами 12 и 19

Быстрая сортировка

Барьерный элемент

4>3

Отсортиро-ванная часть

Отсортированная часть

19>16

Массив отсортирован по возрастанию

по возрастанию

Слайд 18

Быстрая сортировка «Разделяй и властвуй"
Блок-схема алгоритма быстрой сортировки
Параметры блок-схемы
сортируемая последовательность {a[i]}
индекс

ее первого элемента – lb (lower bound - нижняя граница)
индекс ее последнего элемента ub (upper bound - верхняя граница)

Слайд 19

Быстрая сортировка «Разделяй и властвуй"
Блок-схема процедуры разделения массива
Параметры блок-схемы
сортируемая последовательность {a[i]}
индекс

ее первого элемента –
lb (lower bound - нижняя граница)
индекс ее последнего элемента - ub (upper bound - верхняя граница)
рivot – барьерный элемент

Слайд 20

Быстрая сортировка «Разделяй и властвуй"
Довольно сложный анализ эффективности алгоритма быстрой сортировки

Ч. Хоара показал:
в оптимальном случае общее количество сравнений равно C =N*log2N, а общее количество пересылок (присваиваний) M=N*log2N/6

Оптимальный вариант, при котором достигается самая высокая эффективность и минимальная сложность сортировки, обеспечивается выбором в качестве барьера так называемого медианного элемента массива

Слайд 21

Быстрая сортировка «Разделяй и властвуй"
Медианой массива (медианным элементом) считается такой его

элемент, который не меньше одной половины элементов массива и при этом не больше другой половины (независимо от их взаимного положения, важно лишь общее количество элементов)

Так для массива состоящего из 7 элементов, нужно выбрать такой элемент, который окажется не больше трёх любых элементов и при этом не меньше трёх других его элементов
Например, для массива {16, 12, 90, 84, 18, 67, 10} медианой является элемент x5 =18, так как он больше x1=16, x2=12 и x7=10, и при этом меньше чем x3=90, x4=84 и x6=67

Слайд 22

Быстрая сортировка «Разделяй и властвуй"
Выбирать медианный элемент довольно сложно, во всяком

случае такой выбор представляет собой самостоятельную задачу
Удивительное свойство сортировки Хоара -
её средняя производительность при случайном выборе
(в том числе при выборе среднего) барьерного элемента отличается от оптимального всего лишь коэффициентом 2*log102

Слайд 23

Быстрая сортировка «Разделяй и властвуй"

Слайд 24

Быстрая сортировка «Разделяй и властвуй"

Слайд 25

Быстрая сортировка

Слайд 26

Быстрая сортировка «Разделяй и властвуй"

Слайд 27

Улучшение сортировки вставками
Исходное положение:
x[1] x[2] x[3] x[4] x[5] x[6] x[7]

x[8]

1 шаг

Упорядоченная часть

Неупорядоченная часть

2 шаг

< ?

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

Слайд 28

Улучшение сортировки вставками
3 шаг
55
12
42
94
18
67
44
6
12
55
42
94
18
67
44
6
< ?
< ?
44
55
42
94
18
67
12
6
4 шаг
42
44
55
94
18
67
12
6
< ?
< ?
< ?
Сортировка прямыми

вставками

Слайд 29

Улучшение сортировки вставками
Алгоритм сортировки вставками можно слегка улучшить
На каждом шаге внутреннего

цикла проверяются 2 условия
Можно объединить их в одно, поставив в начало массива специальный сторожевой элемент
Он должен быть заведомо меньше всех остальных элементов массива

Вставка сторожевого элемента

Слайд 30

Улучшение сортировки вставками
Отсортированный массив будет не полон, так как из него

исчезло первое число
Для окончания сортировки это число следует вернуть назад, а затем вставить в отсортированную последовательность a[1]...a[n]

Замена сторожевого элемента на a[0] и досортировка массива

Слайд 31

Улучшение сортировки вставками
Функция GetMin( ) - возвращает элемент, заведомо меньший всех

возможных элементов массива, определяется пользователем

Блок-схема
улучшенного алгоритма сортировки вставками

Метод является устойчивым и естественным

Слайд 32

Сортировка методом Шелла
Сортировка включениями с уменьшающимся расстоянием
Сортировка Шелла была названа в

честь ее изобретателя –
Дональда Шелла, который опубликовал этот алгоритм в 1959 году
Основная идея этой сортировки состоит в выполнении нескольких предварительных проходов, на каждом из которых методом прямых вставок сортируются некоторые подпоследовательности элементов массива с заданным шагом k

Такая модификация метода сортировки позволяет быстро переставлять далекие неупорядоченные пары значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов)

В сортировке Шелла элементы каждой из подпоследовательностей упорядочиваются независимо от всех остальных подпоследовательностей

Слайд 33

Сортировка методом Шелла
Сортировка включениями с уменьшающимся расстоянием
Д. Шелл предложил выполнить несколько

таких проходов с разными шагами. Причем, на последнем проходе шаг обязательно должен быть равным единице
То есть на последнем шаге необходимо выполнить самую обычную сортировку прямыми вставками
В первоначально предложенном Д. Шеллом варианте сортировка выполнялась за четыре прохода с шагами 9, 5, 3 и 1

До настоящего времени неизвестно, сколько предварительных проходов нужно сделать для получения наилучших результатов и какие шаги должны быть для этого выбраны
Опытным путем подобраны следующие рекомендуемые шаги по проходам:

1, 4, 13, 40, 121, 364, 1093, 3280, 9841 . . .
1, 8, 23, 77, 281, 1073, 4193, 16577 . . .

1, 3 5, 9, 37, …

1, 3, 7, 15, 31, …

Слайд 34

Сортировка методом Шелла
Пример 1

Слайд 35

Сортировка методом Шелла
Пример 2

Слайд 36

Сортировка методом Шелла
Пример 3
12
8
14
6
4
1
2
3
4
1
2
1 шаг. 4 группы из 2-х элементов
1
7
3
4
12
4
8
9
9
1
14
7
6
2 шаг.

2 группы из 4-х элементов

4<12

8<9

1<14

6<7

4>1

8>6

по возрастанию

4<12

1<4

8<9

6<8

12<14

9>7

8>7

6<7

Слайд 37

Сортировка методом Шелла
Пример 3
4
1
6
3 шаг. 1 группа из 8-ми элементов
Массив отсортирован

по возрастанию

1<6

6>4

1<4

6<7

4<6

7<12

12>8

7<8

12<14

8<12

14>9

12>9

8<9

Слайд 38

Сортировка методом Шелла
Блок-схема алгоритма сортировки Шелла
с выбором шагов, предложенных Кнутом:
…,

121, 40, 13, 4, 1

Слайд 39

Сортировка методом Шелла

Слайд 40

Сортировка методом Шелла

Слайд 41

Эффективность изученных алгоритмов
сортировка вставками со сторожевым элементом

Слайд 42

По результатам замеров производительности методов можно сделать следующие выводы:
Наиболее универсальным

методом, является метод быстрой сортировки («QuickSort»), он показывает стабильно высокие результаты на любых размерах массивов. На втором месте находится метод Шелла. Его использование может быть обосновано более простым алгоритмом с точки зрения программиста
Метод вставки эффективен, при условии большого времени выполнения операций перестановки, так как он является абсолютным лидером по количеству перестановок, проигрывая при этом по количеству сравнений

Эффективность изученных алгоритмов

Слайд 43

По результатам замеров производительности методов можно сделать следующие выводы:
При использовании

небольших массивов данных нет большой разницы по скорости между методами сортировки, поэтому целесообразнее применять метод пузырька или метод вставок
Исследование проводилось на массивах с большой степенью неупорядоченности. Для массивов, которые уже являются почти отсортированными, наиболее применим метод сортировки вставками

Эффективность изученных алгоритмов

Слайд 44

Методы улучшения алгоритмов сортировок. Лекция 7

Содержание

Алгоритм сортировки АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ ОБЫЧНО ПО ВОЗРАСТАНИЮ

Классификация алгоритмов сортировокМетоды внутренней сортировки

Анализ элементарных алгоритмов сортировок

Сортировка Алгоритмы:простые и понятные, но неэффективные для больших массивовметод пузырькаметод выбораметод прямой

551242941867446нетдададададада551242941867446нетдаданетдада551242941867446551242941867446Сортировка обменом / метод пузырька

Методы улучшения сортировки обменомЗапомнить, производился ли на данном проходе какой-либо обмен!Если

Методы улучшения сортировки обменомВвести логическую переменную – признак наличия хотя бы

Методы улучшения сортировки обменом1+2

Методы улучшения сортировки обменомМожно менять направление следующих один за другим проходов

Блок-схемашейкер-сортировкиМетоды улучшения сортировки обменомПараметры блок-схемысортируемая последовательность {a[i]}индекс ее первого элемента –

Методы улучшения сортировки обменомВ лучшем случае, когда массив уже упорядочен, потребуется

Быстрая сортировка «Разделяй и властвуй"В 1962 году Ч.А.Р. Хоар (Charles Antony

Быстрая сортировка «Разделяй и властвуй"СУТЬ СОРТИРОВКИ:Меняем найденные элементы местамиВ случае, если

Быстрая сортировка «Разделяй и властвуй"1. Выберем один из элементов массива -

Пусть a =42 ― барьерный элемент j ― индекс элемента

8>7 переносим в правую часть, т. к. 16>7 не переносим, 4<7

Быстрая сортировка «Разделяй и властвуй"Блок-схема алгоритма быстрой сортировкиПараметры блок-схемысортируемая последовательность {a[i]}индекс

Быстрая сортировка «Разделяй и властвуй"Блок-схема процедуры разделения массиваПараметры блок-схемысортируемая последовательность {a[i]}индекс

Быстрая сортировка «Разделяй и властвуй"Довольно сложный анализ эффективности алгоритма быстрой сортировки

Быстрая сортировка «Разделяй и властвуй"Медианой массива (медианным элементом) считается такой его

Быстрая сортировка «Разделяй и властвуй"Выбирать медианный элемент довольно сложно, во всяком

Быстрая сортировка «Разделяй и властвуй"

Быстрая сортировка «Разделяй и властвуй"

Быстрая сортировка

Быстрая сортировка «Разделяй и властвуй"

Улучшение сортировки вставками Исходное положение: x[1] x[2] x[3] x[4] x[5] x[6] x[7]

Улучшение сортировки вставками 3 шаг551242941867446125542941867446< ?< ?4455429418671264 шаг424455941867126< ?< ?< ?Сортировка прямыми

Улучшение сортировки вставкамиАлгоритм сортировки вставками можно слегка улучшитьНа каждом шаге внутреннего

Улучшение сортировки вставкамиОтсортированный массив будет не полон, так как из него

Улучшение сортировки вставкамиФункция GetMin( ) - возвращает элемент, заведомо меньший всех

Сортировка методом ШеллаСортировка включениями с уменьшающимся расстояниемСортировка Шелла была названа в

Сортировка методом ШеллаСортировка включениями с уменьшающимся расстояниемД. Шелл предложил выполнить несколько

Сортировка методом ШеллаПример 1

Сортировка методом ШеллаПример 2

Сортировка методом ШеллаПример 312814641234121 шаг. 4 группы из 2-х элементов1734124899114762 шаг.

Сортировка методом ШеллаПример 34163 шаг. 1 группа из 8-ми элементовМассив отсортирован

Сортировка методом ШеллаБлок-схема алгоритма сортировки Шелла с выбором шагов, предложенных Кнутом:…,

Сортировка методом Шелла

Сортировка методом Шелла

Эффективность изученных алгоритмовсортировка вставками со сторожевым элементом

По результатам замеров производительности методов можно сделать следующие выводы: Наиболее универсальным

По результатам замеров производительности методов можно сделать следующие выводы: При использовании

вставка выбор обмен метод ШеллаЭффективность изученных алгоритмов

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

Алгоритм сортировки
АЛГОРИТМ ДЛЯ УПОРЯДОЧЕНИЯ НЕКОТОРОГО МНОЖЕСТВА ЭЛЕМЕНТОВ ОБЫЧНО ПО ВОЗРАСТАНИЮ

Классификация алгоритмов сортировок
Методы внутренней сортировки

Сортировка
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
метод прямой

55
12
42
94
18
67
44
6
нет
да
да
да
да
да
да
55
12
42
94
18
67
44
6
нет
да
да
нет
да
да
55
12
42
94
18
67
44
6
55
12
42
94
18
67
44
6
Сортировка обменом / метод пузырька

Методы улучшения сортировки обменом
Запомнить, производился ли
на данном проходе какой-либо обмен!
Если

Методы улучшения сортировки обменом
Ввести логическую переменную – признак наличия хотя бы

Методы улучшения сортировки обменом
1+2

Методы улучшения сортировки обменом
Можно менять направление следующих один за другим проходов

Блок-схема
шейкер-сортировки
Методы улучшения сортировки обменом
Параметры блок-схемы
сортируемая последовательность {a[i]}
индекс ее первого элемента –

Методы улучшения сортировки обменом
В лучшем случае, когда массив уже упорядочен, потребуется

Быстрая сортировка «Разделяй и властвуй"
В 1962 году Ч.А.Р. Хоар (Charles Antony

Быстрая сортировка «Разделяй и властвуй"
СУТЬ СОРТИРОВКИ:
Меняем найденные элементы местами
В случае, если

Быстрая сортировка «Разделяй и властвуй"
1. Выберем один из элементов массива -

Пусть a =42 ― барьерный элемент
j ― индекс элемента

8>7 переносим в правую часть, т. к.
16>7 не переносим, 4<7

Быстрая сортировка «Разделяй и властвуй"
Блок-схема алгоритма быстрой сортировки
Параметры блок-схемы
сортируемая последовательность {a[i]}
индекс

Быстрая сортировка «Разделяй и властвуй"
Блок-схема процедуры разделения массива
Параметры блок-схемы
сортируемая последовательность {a[i]}
индекс

Быстрая сортировка «Разделяй и властвуй"
Довольно сложный анализ эффективности алгоритма быстрой сортировки

Быстрая сортировка «Разделяй и властвуй"
Медианой массива (медианным элементом) считается такой его

Быстрая сортировка «Разделяй и властвуй"
Выбирать медианный элемент довольно сложно, во всяком

Улучшение сортировки вставками
Исходное положение:
x[1] x[2] x[3] x[4] x[5] x[6] x[7]

Улучшение сортировки вставками
3 шаг
55
12
42
94
18
67
44
6
12
55
42
94
18
67
44
6
< ?
< ?
44
55
42
94
18
67
12
6
4 шаг
42
44
55
94
18
67
12
6
< ?
< ?
< ?
Сортировка прямыми

Улучшение сортировки вставками
Алгоритм сортировки вставками можно слегка улучшить
На каждом шаге внутреннего

Улучшение сортировки вставками
Отсортированный массив будет не полон, так как из него

Улучшение сортировки вставками
Функция GetMin( ) - возвращает элемент, заведомо меньший всех

Сортировка методом Шелла
Сортировка включениями с уменьшающимся расстоянием
Сортировка Шелла была названа в

Сортировка методом Шелла
Сортировка включениями с уменьшающимся расстоянием
Д. Шелл предложил выполнить несколько

Сортировка методом Шелла
Пример 1

Сортировка методом Шелла
Пример 2

Сортировка методом Шелла
Пример 3
12
8
14
6
4
1
2
3
4
1
2
1 шаг. 4 группы из 2-х элементов
1
7
3
4
12
4
8
9
9
1
14
7
6
2 шаг.

Сортировка методом Шелла
Пример 3
4
1
6
3 шаг. 1 группа из 8-ми элементов
Массив отсортирован

Сортировка методом Шелла
Блок-схема алгоритма сортировки Шелла
с выбором шагов, предложенных Кнутом:
…,

Эффективность изученных алгоритмов
сортировка вставками со сторожевым элементом

По результатам замеров производительности методов можно сделать следующие выводы:
Наиболее универсальным

По результатам замеров производительности методов можно сделать следующие выводы:
При использовании

вставка выбор обмен метод Шелла
Эффективность изученных алгоритмов