Сортировка вставками
Сортировка вставками — интерактивный эксперимент из приложения «Алгоритмы в действии», бесплатной симуляции StudyFi Lab, которая работает прямо в браузере.
Сортировка вставками похожа на упорядочивание карт в руке: левая часть уже отсортирована, а каждый следующий элемент (key) сдвигается влево, пока не встретит меньший. Большие элементы при этом сдвигаются на одно место вправо. На случайных данных это O(n²), а на почти отсортированных — почти O(n): отсортированному массиву нужно всего n−1 сравнений.
Попробуй: Запусти её на почти отсортированном массиве, а затем на обратном. Во сколько раз больше сдвигов нужно обратному?
Частые вопросы
Что показывает эксперимент «Сортировка вставками»?
Сортировка вставками похожа на упорядочивание карт в руке: левая часть уже отсортирована, а каждый следующий элемент (key) сдвигается влево, пока не встретит меньший. Большие элементы при этом сдвигаются на одно место вправо. На случайных данных это O(n²), а на почти отсортированных — почти O(n): отсортированному массиву нужно всего n−1 сравнений.
Как попробовать «Сортировка вставками»?
Запусти её на почти отсортированном массиве, а затем на обратном. Во сколько раз больше сдвигов нужно обратному?
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.