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

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

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

Сортквання вибором

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

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

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

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

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

procedure TForm1.Button1Click(Sender: TObject);
var
X, Y: array[0..6] of integer;
i, j, min_i, max, min: 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 максимальний елемент
max := X[0];
for i := 0 to StringGrid1.ColCount — 1 do
if (max < X[i]) then
max := X[i];
// Заповнення допоміжного масиву Y відповідними значеннями та вивід його у компоненті StringGrid2
for i := 0 to StringGrid1.ColCount — 1 do
begin
min := X[0];
min_i := 0;
for j := 0 to StringGrid1.ColCount — 1 do
if (min > X[j]) then
begin
min := X[j];
min_i := j;
end;
Y[i] := min;
X[min_i] := max;
StringGrid2.Cells[i, 0] := IntToStr(Y[i]);
end;
end;

Далі, зберігши, відкомпілювавши та запустивши проект на виконання, скориставємось кнопкою «Сортувати». В результаті отримаємо:

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

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

Відмітимо, що розглянутий варіант сортування масиву методом вибору, попри свою простоту, володіє двома недоліками:

  1. Для його реалізації потрібно додатковий масив.
  2. Для знаходження мінімального елемента і його індексу на кожному проході доводиться переглядати всі елементи масиву.

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

Сортування вибором без використання допоміжного масиву

Сортування вибором без використання допоміжного масиву

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

procedure TForm1.Button2Click(Sender: TObject);
var
X: array[0..6] of integer;
i, j, min_i, с, min: 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 здійснюємо його сортування та вивід в компоненті StringGrid2
for i := 0 to StringGrid1.ColCount — 1 do
begin
min := X[i];
min_i := i;
for j := i + 1 to StringGrid1.ColCount — 1 do
if (min > X[j]) then
begin
min := X[j];
min_i := j;
end;
c := X[i];
X[i] := X[min_i];
X[min_i] := c;
StringGrid2.Cells[i, 0] := IntToStr(X[i]);
end;
end;

Далі, знову-таки збережемо, відкомпілюємо та запустимо delphi-проект на виконання. Після того, у вікні, що відкриється, скористаємось кнопкою «Сортувати без допоміжного масиву». Результати роботи програми містяться на наступній формі:

sortuvannja_vyborom4

Сортування вибором без використання допоміжного масиву

Отже, на цьому розгляд алгоритму сортування одновимірного масиву методом вибору завершуємо. Лише відмітимо, що скачати створений в даному парагряфі delphi-проект можна перейшовши за посиланням Сортування вибором на delphi.

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

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

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

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

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

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