Описание тега insertion-sort

Описание тега Вопросы с тегом
Сортировка вставкой - это алгоритм сортировки с временной сложностью в наихудшем случае O(n²) и временной сложностью в лучшем случае (n). Он создает окончательный массив, перемещая элементы вверх в отсортированную позицию по одному.

В отличие от многих алгоритмов сортировки с квадратичной временной сложностью, он фактически применяется на практике для сортировки небольших массивов данных.

Массив виртуально разделен на две части - отсортированный префикс и несортированный суффикс. В начале отсортированная часть содержит первый элемент массива, а несортированная - все остальные. На каждом шаге алгоритм берет первый элемент в неотсортированной части и вставляет его в нужное место в отсортированной части. Когда неотсортированная часть становится пустой, алгоритм останавливается.

Этот алгоритм очень эффективен для данных, которые уже упорядочены или почти упорядочены. Время выполнения равно O(n), если расстояние, на которое должен переместиться любой элемент, ограничено константой.

Ссылки