Алгоритми впорядкування табличних величин (43-5)

Мета уроку: дати учням поняття про сортування табличних величин (масивів). Ознайомити з сортуванням методами: «бульбашки» і «прямого вибору». Виховати наполегливість, спостережливість, розвинути логічне та абстрактне мислення.

Тип уроку: урок вивчення нового матеріалу.

Обладнання: проектор

Література для учнів:

Верлань А.Ф, Апатова Н.В. “Інформатика 10-11”.

Література для вчителя:

• 1. Симонович “Інформатика. Базовий курс”.
• 2. Руденко “Практичний курс інформатики”.
• 3. Макарова “Інформатика 10-11”.
• 4. Андрей Ставровский “Турбо Паскаль”.

Хід уроку

1. Організаційна частина. (2 хв)

• Перевірка відсутніх і готовність учнів до заняття.
• Учитель записує на дошці тему: “Алгоритми впорядкування табличних величин.

2. Актуалізація опорних знань. (10 хв)

Вчитель задає учням питання по попередній темі і проводить фронтальне опитування. Якщо учень відповідає невірно, вчитель пропонує комусь із учнів виправити відповідь товариша.

• 1) Що таке таблиця?

(Таблиця – впорядкована послідовність змінних одного типу, яким надане спільне ім’я.)

• 2) Які бувають таблиці?

(Лінійні і прямокутні)

• 3) Як описуються таблиці на НАМ?

(Тип Таб <назва> [1:10])

• 4) Як описуються масиви на мові програмування Паскаль?

(var A:array [1..10] of real)

• 5) Які масиви називаються квадратичними матрицями?

(У яких кількість стовпців дорівнює кількості рядків)

• 6) Як, на мові програмування Паскаль, за допомогою циклу ввести дані в лінійний масив?

( For i=1 to n do readln(A[i]); )

• 7) Як, на мові програмування Паскаль, за допомогою циклу ввести дані в прямокутний масив масив?

( For i=1 to n do For j=1 to m do readln(A[i,j]); )

• 8) Які ви знаєте алгоритми для роботи з таблицями і масивами?

(Алгоритми знаходження суми і добутку елементів таблиці, алгоритми знаходження найбільшого і найменшого елемента таблиці.)

3. Пояснення нового матеріалу: (25 хв)

Вчитель пропонує дітям записати в зошит число, „Класна робота”, тему сьогоднішнього уроку “Алгоритми впорядкування табличних величин.”, план уроку (демонструється слайд №2):

На попередніх уроках ми з вами розглядали табличні величини (масиви). І ви вже знаєте, що масиви використовують коли потрібно занести якусь інформацію у вигляді таблиці. Наприклад, на метеостанціях кожен час вимірюють температуру повітря і значення вимірів за добу записуються в таблицю. (слайд №3).

Уявіть тепер, що нам потрібно знайти найбільшу та найменшу температуру за добу. Ми можемо скористатися алгоритмом пошуку найбільшого елемента та алгоритмом пошуку найменшого елемента. А тепер уявіть, що в нас елементи таблиці розміщені по зростанню. (див слайд 3). То який елемент таблиці буде найбільшим, а який – найменшим. Останній елемент буде найбільшим, а перший – найменшим. Таблиця в якій елементи розміщенні по зростанню або спаданню називається впорядкованою або відсортованою. А сам процес розміщення елементів по зростанню (спаданню) називається сортуванням. Отож: Сортування – це процес розміщення елементів таблиці (масиву) по зростанню або спаданню. Є такі алгоритми сортування масивів: (див слайд 4)

Ми з вами розглянемо найпростіший (і найгірший з погляду витрат часу) спосіб сортування масиву. Нехай А[1], А[2], ... , А[n] – масив з довільними значеннями елементів. Порівняємо А[1] і А[2]: якщо А[1] А[2], то поміняємо їхнього значення місцями. Потім порівняємо А[2] А[3] і при необхідності обміняємо їхнього значення. У результаті А[3] має найбільше значення серед А[1], А[2], А[3]. Для всіх і від 1 до n-1 виконати Якщо А[i]>A[i+1], то Значення А[i] і A[i+1] обмінюються Якщо значення елементів розглядати як розміри бульбашок, то ці порівняння й обміни схожі на те, як великі бульбашки відтискують менші вниз і спливають на верх. Тому найбільша бульбашка стає верхньою, тобто останній елемент А має найбільше значення. Наприклад, послідовність значень 3, 4, 2, 1 перетвориться в 3, 2, 1, 4. Далі почнемо всі спочатку і перемістимо другий по величині елемент в передостанній елемент А(n-1), перетворивши, наприклад 3,2,1,4 у 2,1,3,4. Потім третє по величині значення перемістимо в А(n-2) і т.д. На останньому кроці порівнюються лише А1 і А2 (їхні значення обмінюються при необхідності). Метод полягає у відшуканні найбільших значень елементів масиву і перестановці їх на початок масиву. Давайте тепер запишемо даний алгоритм на НАМ: (вчитель або один з учнів робить це на дошці – решта в зошитах, або для зменшення затрат часу - демонструється слайд презентації ). (див слайд 5).

Давайте тепер розглянемо даний алгоритм на мові програмування Паскаль. (див слайд 6).

Давайте тепер розв’яжемо задачу з використанням сортування масивів. Отже, запишіть умову задачі.

Нехай задано масив з десяти елементів цілого типу. Відсортувати даний масив по зростанню, і вивести відсортований і несортований масиви. Дані в масив вводити з клавіатури.

Program SortMas;

uses wincrt;

Var A:array [1..10] of integer; i, j, t:integer;

begin

{Введення елементів масиву}

WriteLn('Введіть елементи масиву:');

for I:=1 to 10 do

begin

Write('Введіть',I,'-й елемент:');

ReadLn(A[i]);

End;

{Виведення несортованого масиву}

WriteLn(‘несортований масив:');

For i:=1 to 10 do

write(A[i],' ');

Writeln;

{Сортування масиву по зростанню}

for i:=1 to 9 do

for j:=1 to 10-i do

if A[j]>A[j+1] then

begin

t:=A[j+1];

A[j+1]:=A[j];

A[j]:=t;

end;

{Виведення сортованого масиву}

WriteLn('Сортований масив по зростанню:');

For i:=1 to 10 do

write(A[i],' ');

end.

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

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

Наприклад, даний такий масив: 12 -8 0 30 5 100

Розбиваємо його на дві частини. До першої входить єдиний впорядкований елемент {12}, а до другої - всі останні {-8 0 30 5 100}. Запишемо тепер процес впорядкування по етапах:

І етап: елемент, що впорядковується = -8. 1) -8 < 12, тому виконується обмін, тобто після першого кроку масив має наступний вигляд: -8 12 0 30 5 100 На цьому цикл припиняє свою роботу, тому що досягнуто початок масиву (і=1).

ІІ етап: елемент, що впорядковується = 0. 1) 0 < 12, значить виконується обмін, тобто після першого кроку масив має вигляд: -8 0 12 30 5 100 2) 0 > -8 , значить обмін не виконується, здійснюється вихід з циклу, масив залишається без змін.

ІІІ етап: елемент, що впорядковується = 30. 1) 30 > 12, вхід до циклу не відбувається, масив залишається без змін.

ІV етап: елемент, що впорядковується = 5.

1) 5 < 30, виконується обмін, після перестановки масив має вигляд: -8 0 12 5 30 100

2) 5 < 12, здійснюється обмін, масив набуває вигляду: -8 0 5 12 30 100

3) 5 > 0, цикл припиняє свою роботу, масив залишається без змін.

V етап: елемент, що впорядковується = 100.

1) 100 > 30, вхід до циклу не відбувається, тому що умова відразу хибна і масив залишається без змін. Завдання: написати програму, що реалізовує вище описане завдання.

Program Insert;

Const N=20;

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

i,j,Rez:integer;

Begin

For i:=2 to N do

Begin

j:=i;

{Цикл працює доки, лівий елемент більший за правий та не досягнуто початок масиву}

while (j>1) and (Mas[j]<Mas[j-1]) do

Begin

Rez:=Mas[j];

Mas[j]:=Mas[j-1];

Mas[j-1]:=Rez;

j:=j-1;

End;

End;

End.

Закріплення нового матеріалу. (8 хв)

• 1) Що таке сортування?

(Сортування – це процес розміщення елементів таблиці (масиву) по зростанню або спаданню.)

• 2) Які ви знаєте способи сортування масивів?

(Бульбашкове сортування, пірамідальне сортування і швидке сортування).

• 3) Чому бульбашкове сортування так називається?

(Тому що найбільші елементи ніби “спливають”, як бульбашки)

• 4) Для чого потрібно сортувати масиви?

(Для кращої роботи з даними, що занесені в масив).

• 5) Як на НАМ описується бульбашкове сортування?

Для і від 1 до n

Пц

Для j від 1 до n

Пц

Якщо A[j]>A[j+1] то

t:=A[j+1];

A[j+1]:=A[j];

A[j]:=t;

Кякщо

Кц

Кц)

• 6) Як на мові Паскаль описується бульбашкове сортування?

for i:=1 to n-1 do

for j:=1 to n-i do

if A[j]>A[j+1] then

begin

t:=A[j+1];

A[j+1]:=A[j];

A[j]:=t;

end;

4. Домашнє завдання. (3 хв)

Домашнім завданням пропоную відповідний параграф з підручника Верлань А.Ф, Апатова Н.В. “Інформатика 10-11” та конспект уроку. Даю можливість записати зміст домашнього завдання учням в щоденник.

5. Підсумок уроку. (2 хв)

„ Отже, сьогодні ми познайомилися з сортуванням масивів. Розглянули такі способи сортування масивів як бульбашкове сортування і метод прямого вибору. До мене є якісь запитання? На наступних уроках ми розглянемо інші методи сортування масивів ”