Сортировка вставкой или включением.

Суть алгоритма в следующем – элементы массива разделяют на упорядоченную часть А[1], А[2], ……, А[i-1], которая располагается в начале массива, и остальную, неупорядоченную часть А[i], ……., А[N], а затем, по одному, элементы из неупорядоченной части переносятся в упорядоченную.

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

Рисунок 8.15 - Алгоритм сортировки по возрастанию методом вставки

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

Как видно из рисунка 8.15, в алгоритме есть два цикла.

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

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

Возможность вставки элемента определяется одним из двух условий.

– mas[j-1] <= buf < mas[j] и 1 < j < i, т.е. найдено место внутри упорядоченной последовательности.

– j=1, т.е. tmp является самым малым элементом и вставляется на первое место в упорядоченной части массива.

После завершения цикла сдвигов элемент массива из переменной tmp переносится на найденное место в упорядоченной последовательности.

8.1.3.1 Пример сортировки массива по возрастанию методом вставки

Результаты последовательных шагов сортировки представлены на рисунках 8.16 ‑ 8.20.

Рисунок 8.16 – Исходное разбиение массива при сортировке методом вставки

 

 

Рисунок 8.17 – Результаты выполнения первого шага сортировки вставкой

 

Рисунок 8.18 – Результаты выполнения второго шага сортировки вставкой

 

Рисунок 8.19 – Результаты выполнения третьего шага сортировки вставкой

 

Рисунок 8.20 – Результаты выполнения четвертого шага сортировки вставкой

8.1.3.2 Процедура сортировки методом вставки

procedure SortInsert(var a:TArray100; count: integer);

var i, j, x: integer;

Begin

for i:= 2 to count do

Begin

// Сравниваем элементы на границе между

// упорядоченной и неупорядоченной частями массив а

if a[i] < a[i-1] then

Begin

// Порядок нарушен, запоминаем i-й элемент

x:= a[i];

// Начинаем цикл сдвигов вправо на место i-го элемента

j:= i; // j – индекс вакантного места

Repeat

// сдвигаем вправо

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

j:=j-1;

// пока слева не появилось меньшее число,

// или дошли до начала массива

until (j = 1) or (a[j-1] <= x);

//'Теперь вставим бывший i-й элемент на новое место с индексом j

a[j]:= x;

end;

end;

end;

8.2 Сортировка по усложненным правилам

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

Однако в некоторых случаях необходимо использовать более сложные критерии сравнения элементов, чем простое сравнение. В этих случаях целесообразно написать функцию сравнения элементов по заданному правилу, которая будет возвращать true, если порядок следования элементов не нарушен и false в противном случае. Эту функцию следует вызывать в тех местах процедуры сортировки, где требуется сравнение элементов.

Например, пусть правило сортировки массива целых чисел сформулировано таким образом: «Вначале четные числа по убыванию, а затем нечетные по возрастанию».

Функция, которая сравнивает элементы в соответствии с таким правилом, приведена ниже.

function GoodDisposition(x1, x2: integer): boolean;

Begin

if (x1 mod 2) <> (x2 mod 2) then

//Случай, когда одно число четное, а другое нечетное

//В этом случае четное число считается меньшим

result:= (x1 mod 2) < (x2 mod 2)

else if x1 mod 2 = 0 then

// Случай, когда оба числа четные

result:= x1 > x2

else // Случай, когда оба числа нечетные

result:= x1 < x2;

end;

Теперь с помощью созданной функции можно отсортировать массив в требуемом порядке. Метод сортировки может быть любым. Для примера используем сортировку выборм.

procedure SortChoise (a: TArray100; count: integer);

var i, j, x: integer;

Begin

for i:= 1 to count-1 do

Begin

for j:= i + 1 to count do

if not GoodDisposition(a[i], a[j]) then

Begin

x:= a[i];

a[i]:= a[j];

a[j]:= x;

end;

end;

end;

8.3 Обработка упорядоченных массивов

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

– Добавление элемента в массив, без нарушения порядка

– Объединение двух массивов в один с сохранением порядка

– Поиск позиции элемента в массиве

– Удаление элемента из массива

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