Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.

Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k - м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть

а ≤ а ≤ ... ≤ a .

Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j (1 ≤ j ≤ k -1), что а [j] ≤ a[k] < a. Затем вставить элемент а [k] на найденное место.

С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.

Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения

1 - й шаг

13 6 8 11 3 1 5 9 15 7 Рассматриваем часть массива из одного эле-

мента (13). Нужно вставить в нее второй

элемент массива (6) так, чтобы упорядочен-

ность сохранилась. Так как 6 < 13, вставляем

6 на первое место. Отсортированная часть

массива содержит два элемента (6 13).

3 - й шаг

6 8 13 11 3 1 5 9 15 7 Следующий элемент - 11. Он записывается в упорядоченную часть массива на третье место, так как 11 > 8 , но 11 < 13.

5 - шаг

3 6 8 11 13 1 5 9 15 7 По той же причине 1 записываем на первое

6 - шаг

1 3 6 8 11 13 5 9 15 7 Так как 5 > 3, но 5 < 6 то место 5 в упоря-

Доченной части - третье.

7 - шаг

1 3 5 6 8 11 13 9 15 7 Место числа 9 - шестое.

8 - шаг

1 3 5 6 8 9 11 13 15 7 Определяем место для предпоследнего

Элемента 15. Оказывается, что этот эле-

мент массива уже находится на своем месте.

9 - шаг

1 3 5 6 8 9 11 13 15 7 Осталось подобрать подходящее место для

Последнего элемента (7).

1 3 5 6 7 8 9 11 13 15 Массив отсортирован полностью.

Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения:

For k: = 2 To n Do

{ так как начинам сортировку с поиска подходящего места для a, i изменяется от 2 до n }

‘вставить x на подходящее место в a , ..., a[k] ‘

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

· найден элемент a[j] < x, что говорит о необходимости вставки x между a и a[j].

· достигнут левый конец упорядоченной части массива, следовательно, нужно вставить x на первое место.

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

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

program n3; { Сортировка по убыванию }

type ar=array of integer;

procedure sorting3(var a:ar);

var i,j,x,k:integer;

for k:=2 to n do

x:=a[k]; j:=k-1;

while (j>0)and(x>=a[j]) do

writeln("Введите исходный массив:");

for i:=1 to n do read(a[i]);

writeln("Отсортированный массив:");

for i:=1 to n do write(a[i]," ");

Метод вставки с прямым включением можно улучшить, если отыскивать место для вставляемой записи в упорядоченной подтаблице с помощью метода бинарного (дихотомического, двоичного, логарифмического) поиска. Эта модификация метода вставки названа вставкой с бинарным включением.

Рассмотрим j ‑й шаг сортировки (j =2, 3, ..., n ). Если K [ j ]>= K [ j -1] , то упорядоченность не нарушилась и следует перейти к R [ j +1]– ой записи. Если же K [ j ]< K [ j -1] , то R [ j ] запоминается в рабочей переменной (Rab = R [ j ]) и для нее ищется место в упорядоченной части таблицы – в подтаблице. Обозначим нижнюю границу индекса этой подтаблицы через ng , верхнюю - через vg (первоначально ng =1. vg =j-1 ).

Согласно бинарному поиску ключ K [ j ] рассматриваемой записи R [ j ] должен сначала сравниться с ключом K [ i ] записи R [ i ] , находящейся в середине упорядоченной подтаблицы (i=(ng+vg) div 2) . Если K [ j ]> K [ i ], то отбрасывается (то есть больше не рассматривается) левая часть подтаблицы- записи с меньшими ключами (ng = i +1) . Если K [ j ]< K [ i ] , то отбрасывается правая часть подтаблицы - записи с большими ключами (vg = i -1). В оставшейся части подтаблицы поиск продолжается. Процесс деления частей подтаблицы пополам продолжается до тех пор, пока не возникнет одна из следующих ситуаций:

1) K [ j ]= K [ i ] , следовательно, (i+1) -я позиция является местом для рассматриваемой записи. Сдвинем записи R [ i +1], R [ i +2], …, R [ j -1] на одну позицию вправо и освободим тем самым место для вставки (R [ i +1]= Rab ).

2) K [ j ]<> K [ i ] и ng > vg – ключи не совпали, а длина последней подтаблицы равна 1. В этом случае местом для вставки является позиция ng , поэтому записи R [ ng ], R [ ng +1], … , R [ j -1] должны быть сдвинуты на одну позицию вправо (R [ ng ]= Rab ) .

Алгоритм бинарного поиска подробно описан в разделе "Дихотомический поиск по совпадению".

Рассмотрим на примере j -й шаг сортировки (определяется место записи с ключом, равным 9; j =7, K [ j ]=9 ):

Среднее число сравнений для данного метода составляет n log 2 (n) .

Метод двухпутевой вставки

Метод двухпутевой вставки является модификацией метода вставки с прямым включением; он позволяет улучшить характеристики сортировки.

Для реализации этого метода необходим дополнительный объем памяти, равный объему, занимаемому таблицей, подлежащей сортировке (назовем его зоной вывода T ). На первом шаге сортировки в середину зоны вывода (позиция m=(n div 2)+1 ) помещается первая запись таблицы R. Остальные позиции Т пока пусты. На последующих шагах сортировки ключ очередной записи R [ j ] (j =2, 3, …, n ) сравнивается с ключом записи T [ m ] и, в зависимости от результатов сравнения, место для R [ j ] отыскивается в Т слева или справа от T [ m ] методом вставки. При этом должны запоминаться номера самого левого (l ) и самого правого (r ) внесенных в зону вывода элементов. Конечные значения l и r равны 1 и n соответственно.

В алгоритме должны быть учтены также следующие ситуации:

ключ записи R[j] меньше ключа записи T[m] , но l=1 ;

ключ записи R[j] больше ключа записи T[m] , но r=n .

В этих случаях для вставки записи R [ j ] необходимо осуществлять сдвиг записей подтаблицы вместе с записью T [ m ] вправо или влево (используется метод вставки с прямым включением).

Рассмотрим пример сортировки с использованием этого метода.

Пусть исходная последовательность ключей таблицы имеет вид:

24, 1, 28, 7, 25, 3, 6, 18, 8 (n =9, m =(n div 2)+ 1=5)

Номер шага	Зона вывода

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

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

Сортировка методом прямого включения, так же, как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов. Сортировка этим методом производится последовательно шаг за шагом. На k-м шаге считается, что часть массива, содержащая первые k-1 элемент уже упорядочена, то есть. Далее необходимо взять k-й элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое что. Затем надо вставить элемент a[k] на найденное место. С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг. Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента х. Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы а[j], j изменяется от k-l до 1. Такой просмотр закончится при выполнении одного из следующих условий: найден элемент а[j]Пример Коротко опишем фрагмент алгоритма сортировки с помощью прямого включения: For k:= 2 to n do begin x:= a[k]; j:= k-1; { вставить х на подходящее место в a, …, a[k] } { для этого организуем цикл, которые выполняется, пока } { j > 0 и x

Контрольное задание

Написать программу вставки последнего элемента массива после первого отрицательного элемента этого же массива.

Варианты заданий

ВНИМАНИЕ!!! Если явно не указано иное, входные данные (исходный массив) и выходные данные (отсортированный массив) формировать в виде текстового файла, содержащего целые числа! Для всех заданий предварительно написать процедуру сортировки массива методом прямого включения. 1. Дан ряд, содержащий n элементов. Отсортировать их в порядке возрастания, отбрасывая при этом все повторяющиеся элементы. 2. Определить моду данного ряда – значение, встречающееся среди его элементов чаще всего. 3. Исходный набор данных представляет собой последовательность записей, состоящих из фамилии, возраста и стажа работы. Распечатать этот список: 1) в алфавитном порядке; 2) в порядке увеличения возраста; 3) в порядке увеличения стажа работы. 4. Написать процедуру сортировки по убыванию. 5. Дан ряд целых чисел. Получить в порядке возрастания все различные числа, входящие в этот ряд. 6. Дан ряд из n различных целых чисел. Получить различные целые числа такие, что7. Даны целые Найти наибольшее значение в этой последовательности после выбрасывания из нее всех членов со значением8. Даны натуральные Числа – это измеренные в сотых долях секунды результаты n спортсменов в беге на 100 м. Составить команду из четырех лучших бегунов для участия в эстафете 4х100, т. е. указать одну из четверок натуральных чисел i, j, k, l такую, что сумма имеет наименьшее значение. 9. Дано n независимых случайных точек, с координатами (xi; yi), равномерно распределенных в круге радиуса 1 с центром в начале координат. Напишите программу, располагающую точки в порядке возрастания расстояния от центра. 10. Даны n целых положительных двузначных чисел. Трактуя каждое число как пару цифр из интервала 0–9, отсортировать их (цифры) по возрастанию. 11. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся замкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Подсказка. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу. 12. Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вбитые в доску гвозди - их выпуклая оболочка.) Указание. Упорядочим точки. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек.

Сортировка - это расположение данных в памяти в регулярном виде по выбранному параметру. Регулярность рассматривают как возрастание (убывание) значения параметра от начала к концу массива данных.

При обработке данных важно знать информационное поле данных и размещение их в машине.

Различают внутреннюю и внешнюю сортировку:

Внутренняя сортировка - сортировка в оперативной памяти;

Внешняя сортировка - сортировка во внешней памяти.

Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей , то есть делают перестановку указателей, а сам массив не перемещается. Это - метод сортировки таблицы адресов.

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

Мы будем рассматривать только сортировки, не использующие дополнительную оперативную память. Такие сортировки называются «на том же месте» .

Эффективность сортировки можно рассматривать по нескольким критериям:

Время, затрачиваемое на сортировку;

Объем оперативной памяти, требуемой для сортировки;

Время, затраченное программистом на написание программы.

Выделяем первый критерий. Эквивалентом затраченного на сортировку времени можно считать количество сравнений и количество перемещений при выполнении сортировки.

Порядок числа сравнений и перемещений при сортировке лежит в пределах

От О (n log n) до О (n 2);

О (n) - идеальный и недостижимый случай.

Различают следующие методы сортировки:

Строгие (прямые) методы;

Улучшенные методы.

Строгие методы:

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

Метод прямого выбора;

Метод прямого обмена.

Эффективность строгих методов примерно одинакова.

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

Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность.

При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

Суть алгоритма такова:

for i = 2 to n

X = a(i)

Находим место среди а(1)…а(i) для включения х

next i

Есть два алгоритма сортировки методом прямого включения. Первый - без барьера

Алгоритм сортировки методом прямого включения без барьера

for i = 2 to n

X = a(i)

For j = i - 1 downto 1

If x < a(j)

Then a(j + 1) = a(j)

Else go to L

Endif

Next j

L: a(j + 1) = x

next i

return

Недостатком приведенного алгоритма является нарушение технологии структурного программирования, при которой нежелательно применять безусловные переходы. Если же внутренний цикл организовать как цикл while , то необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера.

Алгоритм сортировки методом прямого включения с барьером

for i = 2 to n

X = a(i)

A(0) = x {a(0) - барьер}

J = i - 1

While x < a(j) do

A(j +1) = a(j)

J = j - 1

Endwhile

A(j +1) = x

next i

return

Эффективность алгоритма прямого включения

Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (включая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположены в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.

Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, С max = n(n - 1)/2, т. е. - О (n 2). Количество перестановок M max = C max + 3(n-1), т.е. - О (n 2). Если же массив уже отсортирован, то число сравнений и перестановок минимально: C min = n-1; M min = =3(n-1).

Сортировка с помощью прямого обмена (пузырьковая сортировка)

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

Мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. иллюстрацию на рисунке ниже).

C min = n - 1, порядок О(n),

а перемещения вообще отсутствуют

Сравнительный анализ прямых методов сортировок показывает, что обменная "сортировка" в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно упорядоченных массивов пузырьковая сортировка даже имеет преимущество.

Такой метод широко известен под именем "пузырьковая сортировка".

Алгоритм метода прямого обмена

for j = n to i step -1

if a(j) < a(j - 1) then

В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок fl , который остается в значении false , если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены жирным шрифтом.

fl = true

if fl = false then return

fl = false

for j = n to i step -1

if a(j) < a(j - 1) then

fl = true

Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление во внутреннем цикле.

Эффективность алгоритма сортировки прямым обменом

Число сравнений C max = n(n-1)/2 , порядок О(n 2).

Число перемещений М max =3C max =3n(n-1)/2, порядок О(n 2).

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений

Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже «готовую» последовательность A 1 , A 2 ,…, A i -1 , и «оставшуюся» (не сортированную) часть: A i , A i +1 ,…, A N .

Суть метода заключается в том, что при каждом i-ом шаге (начиная с i = 2), из неотсортированной части извлекается i-ый элемент и помещается в «готовую» часть, при этом он вставляется на нужное место.

Текстовый алгоритм метода:

1. Начало.

2. Выполнить цикл, пока i имеет значения от 2 до N,
шаг = 1:

а) i-ый элемент (A(i)) поместить в ячейку A(0);

б) присвоить j = -1, то есть j равно номеру элемента, находящегося слева от испытуемого (i-го) и таким образом стоящего в «готовой» последовательности;

в) если А(0) ≥ А(j), то элемент А(0) поместить в ячейку А(j+1), иначе элемент А(j) поместить в ячейку А(j+1), уменьшить значение j на единицу и вновь выполнить пункт в).

На рис. 1 представлена блок-схема сортировки методом прямого включения.

Метод работает следующим образом: на i-ом шаге (начиная с i = 2) i-ый элемент помещается в свободную ячейку (например, А(0)). Этот элемент сравнивается со стоящим в «готовой» части слева от него элементом. Если элемент А(0) меньше, то происходит сдвиг вправо сравниваемого (j-го элемента) на одну позицию, после чего для сравнения берется следующий элемент. Если же элемент А(0) при сравнении оказывается не меньше, то он помещается на место, стоящее сразу за сравниваемым элементом.

Рис. 1. Блок-схема сортировки методом прямого включения

На рис. 2 приведен пример выполнения сортировки методом прямого включения.

Исходная последовательность
	А (0)
I = 2
I = 3
I = 4
I = 5
I = 6
I = 7
I = 8
Результат

Рис. 2. Пример сортировки методом прямого включения

Сортировка прямым включением больше подходит для случая, когда сортируемые данные поступают последовательно (одно за другим).

Сортировка методом прямого выбора

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

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

Текстовый алгоритм метода:

1. Начало.

2. Выполнить цикл, пока i имеет значения от 1 до N – 1,
шаг = 1:

а) поместим текущий (i-ый) элемент в какую-нибудь ячейку памяти (Х) и запомним порядковый номер (i) текущего элемента (в переменной К);

б) выполнить цикл, пока j имеет значения от i + 1 (то есть от следующего за i элемента) до N, шаг = +1:

тело цикла: если Х > А(j), то помещаем в ячейку Х элемент А(j) и запоминаем его номер в ячейке К;

в) присвоить А(К) = А(i) и А(i) = Х.

На рис. 3 приведен пример выполнения сортировки методом прямого выбора.

Исходная последовательность	44						06
I = 1		55	12
I = 2			55			18
I = 3				42		55
I = 4					94		44
I = 5						55	94
I = 6							94	67
I = 7

Рис. 3. Пример сортировки методом прямого выбора