Сортування одновимірного масиву вставками

Сортування вставками — третій і останній з простих алгоритмів впорядкування одновимірних масивів. Основна ідея даного методу полягає в тому, що на першому кроці порівнюються другий та перший елемент вихідного масиву. Якщо порядок між ними, в залежності від типу сортування (за зростанням чи за спаданням) порушений, то перший елемент пересувається на одну позицію вправо. Тепер відсортований масив складається з двох елементів.

Продовжуючи ітераційний процес далі, беремо наступний (третій, четвертий і так далі) елемент і по черзі порівнюємо його, починаючи з кінця,  з іншими елементами в уже відсортованому масиві. Якщо порядок між порівнюваними елементами порушений, то міняємо їх місцями, якщо ні, то вставка нового елемента закінчена і переходимо до наступної ітерації.

Сортування вставками

Сортування вставками

Далі, реалізуємо алгоритм сортування вставками в середовищі програмування delphi. Для цього, запустимо delphi, після чого, на головній формі розмістимо наступні компоненти:

Сортування вставками на delphi

Головна форма delphi-проекту "Сортування вставками"

На наступному кроці, перейдемо до обробника події OnClick компонента Button1 («Сортувати»), і в тілі процедури Button1Click запишемо код, з допомогою якого будемо заповнювати одновимірний масива X та таблицю StringGrid1 випадковими значеннями. Після цього, реалізуємо процес сортування масиву X методом вставок, та здійснимо його вивід у в компоненті StringGrid2.

procedure TForm1.Button1Click(Sender: TObject);
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

Сортування одновимірного масиву методом вставок на delphi

Однак відмітимо, що розглянутий алгоритм, як і алгоритм сортування вибором та сортування обміном, володіє певним недостатком. Для знаходження позиції на яку необхідно вставити кожен наступний елемент, даний алгоритм сортування порівнює його з кожним більшим за значенням від нього елементом у відсортованій частини. Для великих масивів такий ланцюжок порівнянь може бути достатньо громіздким, що може призвести до значного збільшення часу виконання програми. Для того, щоб прискорити даний процес, зазвичай використовують так званий методом половинного ділення.

Тобто, на кожній ітерації елемент, який необхідно вставити порівнюється з елементом, що міститься в середині відсортованої частини. Якщо його значення більше від даного елемента, то наступним аналізується елемент із середнім індексом в меншій частині, якщо менше — то в більшій і так далі, поки не залишиться один елемент. Після цього, всі елементи значення яких являються більшими від значення елемента, який необхідно вставити, зсуваються в циклі, і на це місце робиться вставка.

Далі, доповнимо створений на попередньому кроці delphi-проект, ще одною кнопкою типу TButton і на обробник події OnClick даної кнопки реалізуємо процедуру сортування масиву, яка для пошуку місця вставки буде використовувати деяку рекурсивну функцію get_index, що реалізує метод половинного ділення, і яка поступово зменшуватиме область пошуку до шуканого індексу.

function TForm1.get_index(min_index, max_index, el: integer; X: array of integer): integer;
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-проект можна перейшовши за посиланням Сортування вставками на delphi.

Блок-схема алгоритму cортування вставками без використання методу половинного ділення

Метод вставок блок-схема

Блок-схема алгоритму cортування вставками з використання методу половинного ділення

Сортування вставками блок-схема

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар