Постановка задачи сортировки. Сортировка вставками. Метод простых вставок (метод прямого включения)

3.1. Постановка задачи сортировки

Пусть имеется последовательность из элементов

Каждой записи последовательности поставлен в соответствие ключ , управляющий процессом сортировки. Наряду с ключом, элементу может соответствовать иная информация, не влияющая на процесс сортировки.

Ставится задача: определить такую перестановку , после которой ключи расположились бы в порядке не убывания:

3.2. Сортировка вставками

Данный способ сортировки предполагает, что при рассмотрении записи предыдущие уже упорядочены и элемент вставляется в соответствующее место этой последовательности. Существуют различные модификации этого способа сортировки, некоторые из которых рассмотрены ниже.

Метод простых вставок (метод прямого включения)

Суть метода заключается в том, что из сортируемой последовательности выбирается и анализируется каждый элемент, который помещается «на свое место» в уже отсортированной части последовательности. Принято считать, что элементы, расположенные слева от проверяемого элемента отсортированы в нужном порядке (однако окончательной позиции на промежуточных итерациях эти элементы еще не занимают так как могут быт передвинуты при вставке других элементов). Окончательные позиции элементы займут после проверки всех элементов последовательности.

Данный метод очень прост, однако его нельзя считать эффективным.

Пример сортировки вставками массива ( ) приведен на рисунке 3.1.

Итерация i

⇐ Предыдущая 123 Следующая ⇒