Алгоритми впорядкування табличних величинПлан конспект уроку з інформатики на тему УРОК 5 Тема уроку: Алгоритми впорядкування табличних величин Навчальна мета: Дати поняття про впорядкування табличних величин та методи впорядкування. Навчити розв.язувати задачі, що потребують сортування Розвиваюча мета: розвивати увагу, логічне мислення та спостережливість учнів Виховна мета: виховувати в учнів увагу при роботі в комп»ютерному класі Тип уроку: урок формування нових знань Наочність: таблиці Хід уроку Дуже часто при розв.язуванні задач, пов.язаних з обробкою масивів, необхідно виконувати сортування його елементів за зростанням або спаданням. Такі задачі мають велике практичне значення. Розглянемо деякі з методів, що дозволяють впорядкувати елементи таблиць. Всі існуючі методи сортування можна поділити на три групи: обмінні сортування - виконується обмін між собою двох деяких (найчастіше сусідніх) елементів масивів, якщо відповідні елементи розташовані у вихідному масиві невірно. процес повторюється або певну кількість разів, або доки при черговому проході елементи в масиві не будуть переставлятися. методи прямого вибору - в масиві вибирається елемент з певними властивостями (наприклад, мінімум або максимум), а потім вибраний елемент становиться на своє місце. методи прямої вставки - послідовно вибирається елемент з масиву і після визначення його місця у впорядкованому наборі даних вставляється безпосередньо на своє місце. Приклад 1 Скласти програму впорядкування масиву А[1..N] по зростанню. Метод сортування |бульбашки| Найбільш відомим обмінним сортуванням являється метод |бульбашки|. В ньому при послідовному проході по масиву порівнюються два сусідніх елементи. Якщо їх розміщення являється неправильним (наприклад, при впорядкуванні за зростанням лівий елемент більший за правий), виконується взаємообмін елементів. Процес повторюється щонайменше N-1 разів, де N - кількість елементів в масиві. Простіший алгоритм |бульбашки| має наступний вигляд : Program Porjdok. {Сортування за зростанням} Const n=16. Var i,j:integer. {i,j - змінні циклу} c:integer. {c - додаткова змінна для обміну елементів масиву між собою} a:array [1..n] of integer. Begin For i:=1 to n do Begin write(.a[.,i,.]=.). readln(a[i] {Заповнення масиву} End. For i:=1 to n do For j:=1 to n-1 do If a[j]>a[j+1] then Begin {Обмін елементів масиву через третю змінну} c:=a[j]. a[j]:=a[j+1]. a[j+1]:=c. End. For i:=1 to n do writeln(.a[.,i,.]=.,a[i]). {Вивід масиву} End. Даний метод можна модифікувати, зменшуючи діапазон сортування після кожного проходу. Оскільки, після кожного проходу максимальний елемент масиву буде |спливати наверх|, тобто займати спочатку останню позицію таблиці, потім передостанню і таке інше (дивись таблицю1), то за слідуючим проходом, розглядати останні впорядковані елементи не доцільно. Таблиця 1 Елементи масиву Початковий масив Прохід 1 Прохід 2 Прохід 3 Прохід 4 Прохід 5 Прохід 6 Прохід 7 Прохід 8 A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11] A[12] A[13] A[14] A[15] A[16] 7 2 9 1 16 4 15 5 11 6 3 8 10 12 14 13 2 7 1 9 4 15 5 11 6 3 8 10 12 14 13 16 2 1 7 4 9 5 11 6 3 8 10 12 14 13 15 16 1 2 4 7 5 9 6 3 8 10 11 12 13 14 15 16 1 2 4 5 7 6 3 8 9 10 11 12 13 14 15 16 1 2 4 5 6 3 7 8 9 10 11 12 13 14 15 16 1 2 4 5 3 6 7 8 9 10 11 12 13 14 15 16 1 2 4 3 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Основна ідея алгоритму розв»язання цієї задачі: найбільше у масиві А число поставити в кінець масиву, тобто на N-те місце. Після цього таку саму процедуру треба виконати над елементами масиву від 1-го до (N-1)-го, наступного разу з елементами від 1-го до (N-2)-го і т.д. Отже, треба організувати два вкладені цикли: у внутрішньому циклі щоразу найбільший елемент ставиться в кінець масиву, зовнішній цикл після кожного завершення роботи внутрішнього циклу зменшує кількість елементів масиву А на одиницю. Складовою частиною цього алгоритму є порівняння двох елементів масиву, які стоять поряд. Якщо k-й елемент масиву більший за (k+1)-й, то їх треба поміняти місцями, якщо ж вони стоять у потрібному порядку, то цей порядок треба залишити. Програма, що виконує описаний вище алгоритм, має наступний вигляд: Program Porjdok_2. {Сортування за зростанням} Const n=16. Var i,j:integer. {i,j - змінні циклу} c:integer. {c - додаткова змінна для обміну елементів масиву між собою} a:array [1..n] of integer. Begin For i:=1 to n do Begin write(.a[.,i,.]=.). readln(a[i] {Заповнення масиву} End. for i:=1 to n-1 do For j:=1 to n-i+1 do if а[j]>а[j+1] then Begin с:=а[j]. a[j]:=а[j+1]. а[j+1]:=с. End. For i:=1 to n do writeln(.a[.,i,.]=.,a[i]). {Вивід масиву} end. Цей метод можна ще модифікувати. Як видно з таблиці 1, вже при 8-му проході масив є впорядкованим, хоча за попереднім методом необхідно здійснити ще 7 проходів. що цього уникнути ми вводимо додаткову змінну булівського типу (прапорець), яка буде фіксувати, при черговому проході була здійснена хоча б одна перестановка елементів чи ні. Якщо при черговому проході ні однієї перестановки не було зроблено, то масив вже відсортований і процес перегляду можна припинити. Будемо вважати прапорець |опущеним| (тобто рівним значенню false), якщо перестановки не відбулося, і |піднятим| (рівним true) - в протилежному випадку. Крім того, не забуваємо, що як і в попередньому випадку, після кожного проходу по масиву найбільший елемент |спливає| наверх, тобто займає свою позицію. Тому вводимо додаткову змінну k, що фіксує праву границю впорядкованості, тобто при першому проході k=1 і ми впорядковуємо всі елементи від 1 до N-1, на другому проході k=2 і будуть впорядковуватись всі елементи від 1 до N-2 (останній елемент вже впорядкований) і так далі. Програма, що виконує описаний вище алгоритм, має наступний вигляд: Program Porjdok_3. {Сортування за зростанням} Const n=16. Var i,j,k:integer. {i,j - змінні циклу, k - змінна, що фіксує праву границю впорядкування} c:integer. {c - додаткова змінна для обміну елементів масиву між собою} Flag:Boolean. {Flag - змінна, що фіксує, відбулася перестановка чи ні} a:array [1..n] of integer. Begin For i:=1 to n do Begin write(.a[.,i,.]=.). readln(a[i] {Заповнення масиву} End. Begin k:=1. Repeat Flag:=false. {Робимо припущення, що масив відсортований, а потім перевіряємо, чи правильним було це припущення, тобто чи немає серед елементів таких, що неправильно розташовані, якщо такі елементи будуть, то ми їх переставляємо і Flag присвоюємо значення true} For i:=1 to N-k do Begin If a[i]>a[i+1] then Begin {Обмін елементів масиву через третю змінну} c:=a[i]. a[i]:=a[i+1]. a[i+1]:=c. Flag:=true. End. End. k:=k-1. Until Flag = false. For i:=1 to n do writeln(.a[.,i,.]=.,a[i]). {Вивід масиву} End. Метод прямого вибору Другим методом сортування є метод прямого вибору. Один з його різновидів полягає в тому, що вибирається максимальний елемент масиву, а потім виконується його обмін з останнім елементом таблиці. Після цього останній елемент вважається впорядкованим і процес повторюється для підмасиву, що містить на один елемент менше за початковий, тобто елементи з 1-го до N-1. Процес повторюється кожен раз для масиву, зменшеного на один елемент. Закінчується він тоді, коли невпорядкований підмасив стає довжиною один елемент. Таким чином, загальна кількість повторень дорівнює, як і в попередньому випадку, N-1 (N - кількість елементів масиву). Програмна реалізація запропонованого методу наведена нижче: Program Porjdok_4. Const N=16. Var i, j, Max, N_Max: integer. a:array [1..n] of integer. Begin For i:=1 to n do Begin write(.a[.,i,.]=.). readln(a[i] {Заповнення масиву} End. For i:=1 to N-1 do Begin Max:=a[1]. {Зберігання еталону максимуму} N_Max:=1. {Зберігання номера максимуму } For j:=2 to N-i+1 do If a[j]>Max then Begin Max:=a[j]. {Перевизначення еталону} N_Max:=j. {Зберігання номеру еталону} End. {Обмін місцями максимуму та останього елементу підмасиву} a[N_Max]:=a[N-i+1]. a[N-i+1]:=Max. End. For i:=1 to n do writeln(.a[.,i,.]=.,a[i]). {Вивід масиву} End. Метод прямої вставки Метод прямої вставки забезпечує вставку кожного елементу невпорядкованого масиву на своє місце у вже впорядкований масив. На початку сортування масив розбивається на два підмасиви, лівий з яких повинен бути впорядкованим, а правий - ні. У невідомому масиві тільки один елемент можна вважати впорядкованим, тому спочатку ліва відсортована частина складається всього з одного елементу. Потім по черзі беруться елементи з другої невпорядкованої частини і для них знаходиться місце вставки в першу частину таке, щоб впорядкованість не порушувалась. Це означає, що при сортуванні за зростанням необхідно знайти таке місце в масиві, де лівий елемент буде меншим або рівним за той, що вставляється, а правий - більшим за той, що вставляється. Після цього в масиві необхідно зробити зсув елементів, щоб звільнити місце, на яке і вставити черговий елемент. Щоб оптимізувати розглянутий алгоритм, можна поєднати зсув елементів з пошуком місця вставляння. Для цього перевірки виконуються в зворотному напрямку від елемента, що потрібно вставити до місця вставки Так як елемент, що вставляється, береться першим з невпорядкованої частини масиву, то ліворуч від нього всі елементи вже впорядковані. Тому фактично необхідно порівнювати даний елемент з усіма лівішими від нього і, якщо даний елемент менший за той, з яким порівнюється, то виконується обмін елементів. Елемент наче |пливе| ліворуч від свого початкового місця розташування і процес цей припиняється, якщо знайдений елемент, не більший за даний, або ми досягли початку масиву. Наприклад, даний такий масив: 4, 1, 2, 5, 3, 6. Розбиваємо його на дві частини. До першої входить єдиний впорядкований елемент {4}, а до другої - всі останні {1, 2, 5, 3, 6 }. Запишемо тепер процес впорядкування по етапах: І етап: елемент, що впорядковується = 1. 1) 1 < 4, тому виконується обмін, тобто після першого кроку масив має наступний вигляд: 1, 4, 2, 5, 3, 6. На цьому цикл припиняє свою роботу, тому що досягнуто початок масиву (і=1). ІІ етап: елемент, що впорядковується = 2. 2 < 4, значить виконується обмін, тобто після першого кроку масив має вигляд: 1, 2, 4, 5, 3, 6. 2) 2 > 1, значить обмін не виконується, здійснюється вихід з циклу, масив залишається без змін. ІІІ етап: елемент, що впорядковується = 5. 5 > 4, вхід до циклу не відбувається, масив залишається без змін. ІV етап: елемент, що впорядковується = 3. 3 < 5, виконується обмін, після перестановки масив має вигляд: 1, 2, 4, 3, 5, 6. 2) 3 < 4, здійснюється обмін, масив набуває вигляду: 1, 2, 3, 4, 5, 6. 3) 3 > 2, цикл припиняє свою роботу, масив залишається без змін. V етап: елемент, що впорядковується = 6. 1) 6 > 5, вхід до циклу не відбувається, тому що умова відразу хибна і масив залишається без змін. Програма, що реалізує даний алгоритм, має вигляд: Program Porjdok_5. Const N=6. Var i, j, с:integer. a:array [1..n] of integer. Begin For i:=1 to n do Begin write(.a[.,i,.]=.). readln(a[i] {Заповнення масиву} End. For i:=2 to N do Begin j:=i. {Цикл працює доки, лівий елемент більший за правий та не досягнуто початку масиву} while (j>1) and (а[j]<�а[j-1]) do Begin {Обмін елементів масиву через третю змінну} с:=а[j]. а[j]:=а[j-1]. а[j-1]:=с. j:=j-1. End. End. For i:=1 to n do writeln(.a[.,i,.]=.,a[i]). {Вивід масиву} End. Підсумок уроку На уроці ми вивчили методи сортування масивів: «бульбашки», прямого вибору та прямої вставки. Крім розглянутих методів сортування існують і інші методи: порозрядне сортування, пірамідальне, зливанням, Шелла, FAQ та інші. Інформацію про них ви можете знайти в Інтернеті за адресою http://algolist.manual.ru. На слідуючому уроці ми практично будемо застосовувати дані методи при розв»язуванні задач. Домашнє завдання : Вивчити методи сортування масивів. Початковий рівень Відсортуйте масив А[1..N] в порядку спадання методом «бульбашки». Середній рівень Відсортуйте масив А[1..N] в порядку спадання модифікованим методом «бульбашки». Достатній та високий рівні Знайдіть значення К-го елемента в порядку спадання в масиві А[1..N]. Завдання до даної теми Впорядкувати масив А[1..N] по спаданню методом прямого вибору. Впорядкувати масив А[1..N] по зростанню методом прямого вибору, шукаючи мінімальний елемент і ставлячи його на початок масиву. Впорядкувати масив А[1..N] по спаданню методом прямої вставки.
