Сортування елементів масиву
Досить часто на практиці доводиться впорядковувати елементи масиву. Для кращого розуміння розглядуваного питання розглянемо таку конкретну задачу, з якою ви всі зустрічались на уроках фізкультури, або точніше – фізичного виховання:
Задача 172.172. Вистроїти учнів класу по зросту – від вищих до нижчих. Для спрощення вважати, що в класі навчаються тільки хлопці.
Розв’язання:Одразу ж відмітимо, що існує багато способів розв’язання даної задачі, ми розглянемо лише декілька, які є найбільш простішими і часто використовуються. Для тих, хто серйозно зацікавився програмуванням рекомендуємо звернутись до відповідної літератури з списку, наведеного в кінці цієї книги.
Спосіб 1-й:Припустимо, що на уроці фізичного виховання в нашому класі присутні лише 10 учнів (для можливості наочного зображення ходу розв’язання). Приведемо таблицю зі значеннями росту учнів у відповідності зі списком, який міститься на відповідній сторінці в класному журналі. Номер комірки приведеної таблиці відповідає порядковому номеру учня в списку. Зроблено це знову ж таки лише тому, щоб простіше було пояснювати спосіб шикування, а не тому, що наш клас знаходиться в концтаборі, де відсутні прізвища і кожен має свій «інвентарний» номер.
У таблицю занесено зріст учнів у сантиметрах. Будемо вважати, що дані про зріст вимірювались з точністю до 1–го см, тобто зріст кожного учня вимірюється цілим числом. Знову ж таки , нижче приведемо номери комірок, які відповідають поки що номеру учня в списку. Нехай учні на початку вишикувались у строю саме по алфавіту. Тоді їх розміщення у строю матиме вигляд:
Тепер спробуємо словесно пояснити спосіб сортування елементів масиву (росту учнів) по спаданню, тобто спочатку повинні стояти учні з більшим зростом, а далі – з меншим. Беремо перший елемент масиву – 172 і порівнюємо його з другим – 165. Так як другий елемент менший за перший, то залишаємо його на місці. Порівнюємо перший елемент – 172 з третім – 180, так як третій елемент більший за перший, то їх необхідно поміняти місцями. Тобто перший елемент стає 180, а третій – 172. Тут необхідно врахувати той факт, що для виконання такої перестановки необхідно використати додаткову змінну, щоб не втратити значення однієї з комірок. Це реалізовується досить просто:
...
b := a[1];
a[1] := a[3];
a[3] := b;
...
Після цього нове значення першої комірки порівнюємо з значенням четвертої і так далі, доки не дійдемо до кінця таблиці. Після цього аналогічні дій повторюємо для значення другої комірки, тобто порівнюємо його зі значенням третьої, четвертої і т.д. На останньому кроці нам необхідно порівняти значення передостанньої комірки зі значенням останньої. Отриманий таким чином масив буде відсортовано по спаданню. Після кожного проходження до кінця масиву значення комірок будуть мати такий вигляд:
| до сорт. | ||||||||||
| 1 прохід | ||||||||||
| 2 прохід | ||||||||||
| 3 прохід | ||||||||||
| 4 прохід | ||||||||||
| 5 прохід | ||||||||||
| 6 прохід | ||||||||||
| 7 прохід | ||||||||||
| 8 прохід | ||||||||||
| 9 прохід |
Жирним шрифтом ми виділили вже відсортовані елементи масиву. Всього при даному способі сортування нам необхідно зробити 9! порівнянь[8]. Розглянутий спосіб сортування називають способом обміну. Програмна реалізація даного способу сортування матиме вигляд:
Program sort1;
uses dos, crt;
const b : array[1..10] of byte =
(172,165,180,174,182,179,183,185,176,181);
var a : array[1..10] of byte;
i, j, n : integer;
k : byte;
begin
clrscr;
for i:=1 to 10 do a[i]:=b[i];
{ Нижче реалізовано алгоритм сортування методом обміну }
n:=10;
for i:=1 to n-1 do
begin
for j := i+1 to n do
if a[i]<a[j] then
begin
k := a[j];
a[j] := a[i];
a[i] := k;
end;
end; { Кінець сортування }
writeln(‘ Відсортований масив з 10 чисел: ’);
for i:=1 to 10 do write(a[i], ‘ ’);
readln;
end.
Отже, при сортуванні методом обміну кожен елемент масиву, починаючи з першого і закінчуючи передостаннім порівнюється з усіма елементами, що стоять за ним, тобто починаючи з наступного і закінчуючи останнім.