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

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

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

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

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

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

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

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

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;

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

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

Однако в некоторых случаях необходимо использовать более сложные критерии сравнения элементов, чем простое сравнение. В этих случаях целесообразно написать функцию сравнения элементов по заданному правилу, которая будет возвращать 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;