2D-сортировка вставками. Реализация.
В предыдущем посте я описал хороший подход к сортировке двумерных массивов, основанный на сортировке вставками. Сегодня вы можете увидеть, как это ведет себя на практике — посмотрите видео. Лично мне нравится такая визуализация алгоритмов.
Простое наблюдение за дроном уже дает пару идей. Он не всегда уходит далеко от точки вставки — и это ключевое свойство сортировки вставкой: работа зависит не только от n, но и от того, насколько «отсортированы» данные. Таким образом, почти отсортированное поле фиксируется на удивление быстро.
Теперь сравните его с двумя другими классическими квадратичными алгоритмами.
Сортировку выбором и пузырьковую сортировку на самом деле не волнует, что находится внутри — они все равно продолжают сканировать всю неотсортированную часть. Вот почему их базовый «бюджет усилий» всегда равен n·(n−1)/2 сравнений, независимо от того, насколько удачны входные данные.
И здесь у нас есть красивый мост от «игрушечного программирования» в «Фермере заменили» к серьезной информатике.
Классический трюк из реальной разработки: quicksort хорош, но глубокая рекурсия и очень маленькие партиции стоят дорого. Поэтому многие реализации останавливают quicksort раньше, оставляют массив «почти отсортированным», а затем добивают его insertion sort.