І Скляр - Я готуюсь до курсу інформатики. Алгоритмізація та програмування

Мета уроку: Дати поняття про методи впорядкування табличних величин. Навчити розв’язувати задачі, що потребують сортування.

Теоретичний матеріал

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

Всі існуючі методи сортування можна поділити на три групи:

• обмінні сортування — виконується обмін між двома (найчастішесусідніми) елементами масивів, якщо відповідні елементи розташовані увихідному масиві невпорядковано; процес повторюється або певну кількість разів, або доки елементи в масиві не стануть впорядкованими;

• методи прямого вибору — в масиві обирається елемент з певнимивластивостями (наприклад, мінімум або максимум), а потім вибранийелемент ставиться на своє місце;

• методи прямої вставки — послідовно вибираються елементи з масивуі після визначення їх місця у впорядкованому наборі даних вставляютьсябезпосередньо на своє місце.

Найбільш відомим обмінним сортуванням є метод «бульбашки».

В ньому при послідовному проході по масиву порівнюються два сусідніх елементи. Якщо їх розміщення є неправильним (наприклад, при впорядкуванні за зростанням лівий елемент більший за правий), виконується взаємообмін елементів. Процес повторюється щонайменше 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 — змінні циклу)

Rez:integer; {Rez - додаткова змінна для обміну елементів масиву між собою)

Begin

For i:=1 to N do

For j:=1 to N-i do

If Mas[j]>Mas[j+l] then

Begin

{Обмін елементів масиву через третю змінну}

Rez:=Mas[j]; Mas[j]:=Mas[j+1]; Mas[j+1]:=Rez;

End;

End.

Зверніть увагу, що в цьому алгоритмі у вкладеному циклі, що безпосередньо здійснює порівняння елементів, змінна циклу змінюється за іншим законом, ніж у попередньому випадку: від 1 до N-i, де і — змінна циклу зовнішньої команди повторення.

Другий метод модифікації алгоритму «бульбашки» полягає в тому, що ми вводимо додаткову змінну булівського типу (так званий прапорець), яка фіксуватиме при черговому проході була здійснена хоча б одна перестановка елементів чи ні. Адже очевидно, що якщо при черговому проході не відбулося жодної перестановки, то масив уже відсортований і процес перегляду можна припинити. Домовимось вважати прапорець «опущеним» (тобто рівним значенню false) , якщо перестановки не відбулося, і «піднятим» (рівним true) — у протилежному випадку. Крім того, як і в попередньому випадку, після кожного проходу по масиву найбільший елемент «спливає» угору, тобто займає своє позицію. Тому вводимо додаткову змінну к, що фіксує праву границю впорядкованості, тобто при першому проході к = 1 і ми впорядковуємо всі елементи від 1 до N- 1, на другому проході к = 2 і будуть впорядковуватись усі елементи від 1 до N- 2 (останній елемент уже впорядкований) і так далі. Програма має вигляд:

Program Bubble; {Сортування за зростанням}

Const N=20;

Var Mas:array[1..N] of integer;

i,j,k:integer; {i,j — змінні циклу, k — змінна, що фіксує праву границю впорядкування}

Rez:integer; {Rez — додаткова змінна для обміну елементів масиву між собою}

Flag:Boolean; {Flag — змінна, що фіксує, відбулася перестановка чи ні}

Begin