Сортування вставками – третій і останній з простих алгоритмів впорядкування одновимірних масивів. Основна ідея даного методу полягає в тому, що на першому кроці порівнюються другий та перший елемент вихідного масиву. Якщо порядок між ними, в залежності від типу сортування (за зростанням чи за спаданням) порушений, то перший елемент пересувається на одну позицію вправо. Тепер відсортований масив складається з двох елементів.
Продовжуючи ітераційний процес далі, беремо наступний (третій, четвертий і так далі) елемент і по черзі порівнюємо його, починаючи з кінця, з іншими елементами в уже відсортованому масиві. Якщо порядок між порівнюваними елементами порушений, то міняємо їх місцями, якщо ні, то вставка нового елемента закінчена і переходимо до наступної ітерації.
Далі, реалізуємо алгоритм сортування вставками в середовищі програмування delphi. Для цього, запустимо delphi, після чого, на головній формі розмістимо наступні компоненти:
На наступному кроці, перейдемо до обробника події OnClick компонента Button1 («Сортувати»), і в тілі процедури Button1Click запишемо код, з допомогою якого будемо заповнювати одновимірний масива X та таблицю StringGrid1 випадковими значеннями. Після цього, реалізуємо процес сортування масиву X методом вставок, та здійснимо його вивід у в компоненті StringGrid2.
var
X: array[0..6] of integer;
i, j, c: integer;
begin
// Заповнюємо масиви X та таблицю StringGrid1 випадковими даними
randomize;
for i := 0 to StringGrid1.ColCount – 1 do
begin
X[i] := Random(100);
StringGrid1.Cells[i, 0] := IntToStr(X[i]);
end;
// Сортуємо масив X
for i := 1 to StringGrid1.ColCount – 1 do
begin
c := X[i];
j := i – 1;
while (j >= 0) and (X[j] > c) do
begin
X[j + 1] := X[j];
j := j – 1;
end;
X[j + 1] := c;
end;
// Виводимо відсортований масив X у компоненті StringGrid2
for i := 0 to StringGrid1.ColCount – 1 do
StringGrid2.Cells[i, 0] := FloatToStr(X[i]);
end;
Далі, зберігши, відкомпілювавши та запустивши проект на виконання, скориставємось кнопкою «Сортувати». В результаті отримаємо:
Однак відмітимо, що розглянутий алгоритм, як і алгоритм сортування вибором та сортування обміном, володіє певним недостатком. Для знаходження позиції на яку необхідно вставити кожен наступний елемент, даний алгоритм сортування порівнює його з кожним більшим за значенням від нього елементом у відсортованій частини. Для великих масивів такий ланцюжок порівнянь може бути достатньо громіздким, що може призвести до значного збільшення часу виконання програми. Для того, щоб прискорити даний процес, зазвичай використовують так званий методом половинного ділення.
Тобто, на кожній ітерації елемент, який необхідно вставити порівнюється з елементом, що міститься в середині відсортованої частини. Якщо його значення більше від даного елемента, то наступним аналізується елемент із середнім індексом в меншій частині, якщо менше – то в більшій і так далі, поки не залишиться один елемент. Після цього, всі елементи значення яких являються більшими від значення елемента, який необхідно вставити, зсуваються в циклі, і на це місце робиться вставка.
Далі, доповнимо створений на попередньому кроці delphi-проект, ще одною кнопкою типу TButton і на обробник події OnClick даної кнопки реалізуємо процедуру сортування масиву, яка для пошуку місця вставки буде використовувати деяку рекурсивну функцію get_index, що реалізує метод половинного ділення, і яка поступово зменшуватиме область пошуку до шуканого індексу.
var
i: integer;
begin
i := min_index + Round((max_index – min_index) / 2);
if (max_index – min_index) <= 1 then
get_index := i + 1
else
if (el < X[i]) then
get_index := get_index(min_index, i, el, X)
else
get_index := get_index(i, max_index, el, X);
end;
procedure TForm1.Button1Click(Sender: TObject);
var
X: array[0..6] of integer;
i, c, k, m: integer;
begin
// Заповнюємо масиви X та таблицю StringGrid1 випадковими даними
randomize;
for i := 0 to StringGrid1.ColCount – 1 do
begin
X[i] := Random(100);
StringGrid1.Cells[i, 0] := IntToStr(X[i]);
end;
// Сортуємо масив X
for i := 1 to StringGrid1.ColCount – 1 do
begin
if (X[i] >= X[i – 1]) then
continue;
if (X[i] < X[0]) then
m := 0
else
m := get_index(0, i, X[i], X);
c := X[i];
for k := i downto m + 1 do
X[k] := X[k – 1];
X[m] := c;
end;
// Виводимо відсортований масив X у компоненті StringGrid2
for i := 0 to StringGrid1.ColCount – 1 do
StringGrid2.Cells[i, 0] := FloatToStr(X[i]);
end;
Далі, знову-таки збережемо, відкомпілюємо та запустимо delphi-проект на виконання. Після того, у вікні, що відкриється, скористаємось кнопкою «Сортувати з використанням методу половинного ділення». Результати роботи програми містяться на наступній формі:
Скачати створений в даному парагряфі delphi-проект можна перейшовши за посиланням Сортування вставками на delphi.
Блок-схема алгоритму cортування вставками без використання методу половинного ділення
Блок-схема алгоритму cортування вставками з використання методу половинного ділення
