Маргинальные свойства простых сортировок целочисленных массивов
15
Метод сортировки
Количество операций
минимальное
максимальное
Метод выбора
2
10 11 3
n n
2
21 7
10
2 2
n n
Метод перестановки
2
2 3 3
n n
2
1 13
2
2 2
n n
Метод парных сравнений
2
1 2 3
n n
2
5 15
1
2 2
n n
Модифицированный метод
парных сравнений
2 6
n
2
4 2 6
n n
Метод сдвига
2
9 10 3
n n
2
13 13
9
2 2
n n
Метод последовательной
вставки
5 7
n
2
23 13
16
2 2
n n
Метод дихотомической
вставки
5 7
n
2
2
17 7
15 9 1 log
2 2
n
n
n n
В наилучшем случае, когда исходный массив уже упорядочен,
т. е. для частично упорядоченных редко сортируемых массивов,
предпочтительными являются
модифицированный метод парных
сравнений
и
методы последовательной
и
дихотомической вставки
.
В наихудшем случае, когда исходный массив упорядочен по
убыванию, предпочтительнее
метод выбора
и
метод дихотомиче-
ской вставки
.
ЛИТЕРАТУРА
[1] Кнут Д.Э.
Искусство программирования. Т. 3: Сортировка и поиск.
Москва,
Вильямс, 2009, 824 с.
[2] Седжвик Р.
Фундаментальные алгоритмы на С++: анализ, структуры
данных, сортировка, поиск.
Санкт-Петербург, ООО «ДиаСофтЮП», 2002,
688 с.
[3] Деон А.Ф., Терентьев Ю.И. Маргинальные свойства сортировки массивов
методом дихотомической вставки.
Инженерный журнал: наука и иннова-
ции,
2013, вып. 6 (18). URL: http:/engjournal.ru/catalog/it/hidden/769.html.
Статья поступила в редакцию 06.11.2014
Ссылку на эту статью просим оформлять следующим образом:
Деон А.Ф., Терентьев Ю.И. Маргинальные свойства простых сортировок це-
лочисленных массивов.
Инженерный журнал: наука и инновации
, 2014, вып. 11.
URL:
