Сортировка вставкой в Python

Тема по КТП

Класс

10 класс

Предмет

Информатика

Четверть

2

Урок

№ 12

Раздел

Алгоритмизация и программирование (Python)

Цели обучения

• 10.2.2.1объяснять принцип работы алгоритмов сортировки (пузырьком, выбором, вставкой) путем сравнения их эффективности
• 10.2.2.2реализовывать алгоритмы сортировки на языке Python

Примеры вопросов

1. 1
   В чём состоит основной принцип сортировки вставкой?

   Массив делят пополам и сортируют каждую часть На каждом шаге выбирают минимальный элемент массива Очередной элемент вставляют в отсортированную часть Соседние элементы меняют местами до полного порядка
2. 2
   Какова средняя временная сложность сортировки вставкой?

   \(O(1)\) \(O(n \log n)\) \(O(n)\) \(O(n^2)\)
3. 3
   В каком случае сортировка вставкой работает за \(O(n)\)?

   Массив заполнен случайными числами Массив отсортирован по убыванию Массив содержит только отрицательные числа Массив уже отсортирован по возрастанию