УРОК 26. Впорядкування таблиць
Мета уроку: Дати поняття про методи впорядкування табличних величин. Навчити розв'язувати задачі, що потребують сортування.
Теоретичний матеріал
Дуже часто при розв'язуванні задач, пов'язаних з обробкою масивів, необхідно виконувати сортування його елементів за зростанням або спаданням. Такі задачі мають велике практичне значення. Розглянемо деякі з методів, що дають змогу впорядкувати елементи таблиць.
Всі існуючі методи сортування можна поділити на три групи:
• обмінні сортування — виконується обмін між двома (найчастіше сусідніми) елементами масивів, якщо відповідні елементи розташовані у вихідному масиві невпорядковано; процес повторюється або певну кількість разів, або доки елементи в масиві не стануть впорядкованими;
• методи прямого вибору — в масиві обирається елемент з певними властивостями (наприклад, мінімум або максимум), а потім вибраний елемент ставиться на своє місце;
• методи прямої вставки — послідовно вибираються елементи з масиву і після визначення їх місця у впорядкованому наборі даних вставляються безпосередньо на своє місце.
Найбільш відомим обмінним сортуванням є метод «бульбашки».
В ньому при послідовному проході по масиву порівнюються два сусідніх елементи. Якщо їх розміщення є неправильним (наприклад, при впорядкуванні за зростанням лівий елемент більший за правий), виконується взаємообмін елементів. Процес повторюється щонайменше N - 1 разів, де N— кількість елементів у масиві.
Найпростіший алгоритм «бульбашки» має наступний вигляд:
Program Bubble ; {Сортування за зростанням}
Const N =20;
Var Mas : array [1 .. N] of integer;
i,j:integer; {i,j — змінні циклу)
Rez: integer; {Rez — додаткова змінна для обміну елементів масиву між собою)
Begin
For i:=1 to N do
For j:=1 to N-l do
If Mas[j]>Mas[j+l] then
Begin
{Обмін елементів масиву через третю змінну)
Rez:=Mas[j]; Mas[j]:=Mas[j+1] ; Mas [ j+1]:=Rez;
End;
End.
Метод можна модифікувати, зменшуючи діапазон сортування після кожного проходу, адже ясно, що після кожного проходу максимальний елемент масиву буде «спливати наверх», тобто займати спочатку останню позицію таблиці, потім передостанню і так далі:
Програма, що реалізує описаний алгоритм має наступний вигляд:
Program Bubble ; {Сортування за зростанням)
Const N=20
Var Mas :аг ay [1..N] of integer ;
і, j:integer; {i,j — змінні циклу)