Лабораторная работа №3

Сортировка методом прямого включения

Цель работы Исследовать сортировку массива методом прямого включения и оценить эффективность этого алгоритма.

Общие сведения

Сортировка методом прямого включения, так же, как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов. Сортировка этим методом производится последовательно шаг за шагом. На k-м шаге считается, что часть массива, содержащая первые k-1 элемент уже упорядочена, то есть. Далее необходимо взять k-й элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое что. Затем надо вставить элемент a[k] на найденное место. С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг. Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента х. Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы а[j], j изменяется от k-l до 1. Такой просмотр закончится при выполнении одного из следующих условий: • найден элемент а[j]<х, что говорит о необходимости вставки х между a[j-1] и a[j]; • достигнут левый конец упорядоченной части массива, следовательно, нужно вставить х на первое место. До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на 1 позицию вправо, в результате чего в отсортированной части будет освобождено место под х.

Пример

Коротко опишем фрагмент алгоритма сортировки с помощью прямого включения:

For k := 2 to n do
  begin
     x := a[k]; j := k-1;
     { вставить х на подходящее место в a[1], …, a[k] }
     { для этого организуем цикл, которые выполняется, пока }
     { j > 0 и x