Сортировка вставкой — это методика сортировки, в которой компоненты исходных данных анализируются по одному, и все вновь поступившие компоненты помещаются в необходимое место между уже прошедшими сортировку компонентами.
Введение
Под сортировкой вставками понимается простой алгоритм, суть которого состоит в том, что на каждом алгоритмическом этапе берётся один компонент массива и для него определяется наиболее подходящее место, куда он и помещается.
Необходимо заметить, что по такой логике, однокомпонентный массив можно считать уже отсортированным. То есть процедура получается следующая. Имеется участок массива, который был ранее отсортирован, и необходимо распределить оставшиеся компоненты массива среди уже отсортированных элементов, но так, чтобы сохранился требуемый порядок. С этой целью, на каждом этапе выполнения алгоритма, выбирается один компонент исходных данных и вставляется в предназначенную ему условиями алгоритма позицию в уже прошедшей сортировку части массива. Это действие повторяется до тех пор, пока не будет осуществлена полная сортировка всех исходных данных.
Методика определения очередного компонента из исходных данных произвольна, но, как правило, компоненты внедряются в порядке их расположения в исходном массиве. Это обеспечивает устойчивость работы сортировочного алгоритма. Поскольку при выполнении алгоритма возможен обмен местами лишь соседствующих компонентов, то каждая операция обмена вызывает уменьшение количества инверсий на один шаг. То есть, число обменных операций равняется числу инверсий во входном массиве не зависимо от того, как выполняется сортировка.
В словесной формулировке, алгоритм выглядит достаточно сложным, но на практике является наиболее простым методом сортировки. К примеру, человеку требуется удобно разложить денежные купюры в своём кошельке для последующего их быстрого обнаружения. Он берёт, например, купюру, достоинством в сто рублей и проверяет расположение остальных купюр в кошельке. Определяет, что там лежат три банкноты, достоинством в десять, пятьдесят и пятьсот рублей. Выбор очевиден, купюра в сто рублей кладётся между пятьдесят и пятьсот. Аналогично при карточной игре, например, в преферанс, игрок интуитивно размещает свои карты в порядке мастей и возрастания достоинства каждой карты.
Реализация сортировки вставкой
Рассмотрим в качестве исходных данных массив целых чисел int. Как известно, номера компонентов массива находятся в диапазоне от нуля до n-1. Реализация алгоритма предполагается на языке С++. Главный цикл алгоритма будет начинаться не с нулевого компонента, а с первого, поскольку нулевой компонент является уже отсортированным массивом, и уже по отношению к нему будет выполняться вставка других компонентов. Ниже приведена программная реализация алгоритма:
Рисунок 1. Программная реализация алгоритма. Автор24 — интернет-биржа студенческих работ
Программа крайне простая, состоящая из трёх строчек. Функция swap выполняет обмен мест компонентов x[j-1] и x[j]. Поиск места, куда вставить компонент, выполняется вложенным циклом.
Сложность сортировки вставками равна $n^2$, а число операций сравнения определяется выражением n • (n - 1) / 2. Доказать эти утверждения поможет следующая программа:
Рисунок 2. Программа. Автор24 — интернет-биржа студенческих работ
Число операций перестановки для ста компонентов приведено ниже:
Рисунок 3. Число операций. Автор24 — интернет-биржа студенческих работ
Видим, что при количестве компонентов, равном ста, число необходимых перестановок равняется только 4950, а не десять тысяч, как даёт расчёт по формуле n2 . Это нужно учитывать при выборе сортировочного алгоритма. Метод сортировки при помощи вставок даёт наибольший эффект, если выполнена частичная сортировка и количество компонентов массива не велико.
Другой вариант алгоритма на С++
Рисунок 4. Программа. Автор24 — интернет-биржа студенческих работ
Оптимизированный вариант алгоритма на С++
Выполнены улучшения алгоритма по следующим пунктам:
- Выполняется определение самого маленького компонента и перемещение его в начало массива (это необходимое условие для выполнения следующего пункта.
- Выполняется возврат их внутреннего цикла, если компонент уже перемещён на нужное место.
- Операция обмена замещена операцией присваивания.
Рисунок 5. Программа. Автор24 — интернет-биржа студенческих работ
