Лекция 15. Математические методы (поиск, сортировка вставкой) (1152917), страница 2
Текст из файла (страница 2)
не требует дополнительнойпамяти.Недостатки: элементы выставляются на «свои отсортированные места»только на последнем шаге алгоритма..9Воробьева И.А. «Информатика. Язык Питон»Пример 11.2. Пример сортировки методом вставки.(серым цветом выделено состояние массива на начало цикла WHILE)НачальноемассиваШаг 1состояние 8 23 5 65 44 33 1 68 23 | 5 65 44 33 1 68 23 5 | 65 44 33 1 6Шаг 2Шаг 3Шаг 48 5 23 | 65 44 33 1 65 8 23 | 65 44 33 1 65 8 23 65 | 44 33 1 65 8 23 65 | 44 33 1 65 8 23 65 44 | 33 1 65 8 23 44 65 | 33 1 65 8 23 65 44 33 | 1 6Шаг 55 8 23 44 33 65 | 1 65 8 23 33 44 65 | 1 65 8 23 65 44 33 1 | 6Шаг 655555188881523 33 44 1 65 | 623 33 1 44 65 | 623 1 33 44 65 | 61 23 33 44 65 | 68 23 33 44 65 | 68 23 33 44 65 | 65 8 23 65 44 33 1 6 |Шаг 711111555558888623 33 44 623 33 6 4423 6 33 446 23 33 448 23 33 4465 |65 |65 |65 |65 | 10Воробьева И.А.
«Информатика. Язык Питон»Посмотрим, сколько шагов потребуется алгоритму в худшем случае.Пример 11.3. Массив, упорядоченный в обратном порядке(худший вариант), длина массивашаг сортировки состояниечислочисломассивасравненийпересылокисходный6 5 4 3 2 1массив111: 5 6 4 3 2 1222: 4 5 6 3 2 1333: 3 4 5 6 2 1444: 2 3 4 5 6 1555: 1 2 3 4 5 6Число шагов алгоритма (сравнений и пересылок) –.–Сложность алгоритма –.Литература:[1]. Методы сортировки и поиска, С.Д.
Кузнецов, ИСП РАН, Центр ИнформационныхТехнологий http://citforum.ru/programming/theory/sorting/sorting1.shtml#2_1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
