ПРОФІЛЬНА ІНФОРМАТИКА 10 КЛАС Масиви. Створення консольних проектів у C# - презентация

1 ПРОФІЛЬНА ІНФОРМАТИКА 10 КЛАС Масиви. Створення консольних проектів у C#

2 Сортування масивів Однією з найбільш поширених операцій обробки масивів є їх упорядкування, або сортування. Упорядкування масиву це зміна порядку розташування його елементів за певним критерієм. Наприклад, числовий масив можна упорядкувати за зростанням значень його елементів або за їх спаданням, а масив рядків можна відсортувати в алфавітному порядку. Найчастіше сортування масиву здійснюється з метою полегшення подальшого пошуку. Відомо багато методів сортування масиву, що відрізняються швидкодією й обсягом оперативної пам'яті, яка при цьому використовується. Серед цих методів можна вирізнити методи внутрішнього та зовнішнього сортування. Методи внутрішнього сортування не передбачають використання допоміжних масивів. Ці методи застосовують до масивів, що повністю розташовані в оперативній пам'яті. Методи зовнішнього сортування застосовують до великих масивів даних, які зберігаються на зовнішніх носіях. У цьому розділі розглянемо методи внутрішнього сортування масиву, обмежуючись задачею сортування за зростанням. Методи внутрішнього сортування прийнято поділяти на дві групи: елементарні (прямі) та удосконалені методи.

3 Сортування масивів Найбільш відомими елементарними методами сортування масиву є: 1) сортування вставкою (включенням); 2) сортування вибором; 3) сортування обміном (бульбашкове сортування). З удосконалених методів сортування найчастіше використовуються такі: 1) швидке сортування, або метод Хоара; 2) сортування включенням зі спадним приростом, або метод Шелла; 3) сортування за допомогою дерева, або пірамідальне сортування; 4) сортування методом злиття.

4 Сортування методом вставки На кожному кроці цього методу масив розділений на дві частини: ліву, вже відсортовану, та праву, ще не відсортовану. Перший елемент правої частини вставляється до лівої частини так, щоб ліва частина залишалася відсортованою. У результаті відсортована частина збільшується на один елемент, а невідсортована - на один елемент зменшується. Отже, на кожному кроці алгоритму сортування методом вставки слід виконати дві операції: пошук позиції для вставки елемента та власне його вставку із подальшим зсувом на одну позицію вправо від елементів відсортованої частини. Цей зсув «затре» перший елемент невідсортованого підмасиву останнім елементом відсортованого. Спочатку відсортованим підмасивом вважаємо перший елемент, а решту елементів масиву відносимо до невідсортованої частини.

5 Алгоритм сортування методом вставки Формалізуємо алгоритм сортування методом вставки. Підмасив, що містить елементи з другого до останнього, вважати невідсортованого частиною. Поки ця частина не стане порожньою, виконувати такі дії. 1. Зберегти перший елемент невідсортованого підмасиву в допоміжній змінній. 2. Визначити позицію вставки збереженого елемента у масив. Для цього дотримуватися перелічених далі вказівок Вважати перший елемент масиву поточним Доки елемент для вставки більше за поточний, збільшувати індекс поточного елемента. 3. Вставити збережений на кроці 1 елемент на знайдену позицію вставки, зсунувши на одну позицію вправо решту відсортованої частини. 4. Пересунути початок невідсортованої частини на одну позицію вправо.

6 Сортування методом вибору Цей метод, як і метод сортування вставкою, розділяє масив на дві частини: ліву, вже впорядковану, та праву, ще не впорядковану. Вибирають найменший елемент невідсортованої частини. Цей елемент міняють місцями з її першим елементом, збільшуючи на одиницю довжину відсортованої частини масиву. Отже, на першому кроці алгоритму невпорядкованою частиною є весь масив, з котрого вибирають мінімальний елемент. Цей елемент міняють місцями з першим елементом масиву. На другому кроці невпорядковану частину масиву складають елементи від другого до останнього. Серед цих елементів вибирають найменший, котрий міняють місцями з другим. Процес триває доти, доки у невідсортованій частині не залишиться один елемент.

7 Алгоритм сортування методом вибору Формалізуємо алгоритм сортування методом вибору. Весь масив вважати невідсортованою частиною. Поки ця частина містить більше одного елемента, виконувати такі дії: 1). Вибрати перший елемент невідсортованої частини масиву і вважати його мінімальним; запам'ятати індекс цього елемента. 2). Для елементів від наступного після вибраного і до останнього повторювати такі дії Порівняти вибраний елемент і поточний Якщо вибраний елемент більший за поточний, запам'ятати поточний елемент як мінімальний, а його індекс як індекс мінімального елемента. 3). Поміняти місцями мінімальний і вибраний на кроці 1 елементи. 4). Пересунути початок невідсортованої частини на одну позицію вправо.

8 Сортування методом обміну Базовою операцією в цьому методі є порівняння двох сусідніх елементів масиву. Якщо їх розташування суперечить умові впорядкування, вони міняються місцями. Послідовне застосування такої операції до всіх пар елементів масиву, від останньої пари до першої, дозволить виявити найменший елемент в першій позиції. Друга назва цього метода бульбашкове сортування пояснюється схожістю процесу обміну місцями сусідніх елементів зі спливанням більшої бульбашки. Під час сортування методом обміну впорядкованою буде ліва частина масиву, а щойно описаний процес повторюється для правої частини, котра на кожній ітерації методу зменшуватиметься на один елемент.

9 Алгоритм сортування методом обміну 1). Установити лічильник ітерацій рівним одиниці. 2). Для елементів масиву, від останнього до елемента з індексом, що дорівнює поточному значенню лічильника ітерацій, повторювати такі дії Якщо поточний елемент більший за попередній, поміняти ці елементи місцями Перейти до попереднього елемента. 3). Збільшити лічильник ітерацій. Якщо значення лічильника дорівнює кількості елементів масиву, завершити сортування.

10 Швидке сортування Автор цього метода Ч. Хоар назвав його швидким сортуванням, оскільки для більшості масивів цей метод потребує приблизно (n/6) log n обмінів елементів і n log n порівнянь, тобто набагато менше, ніж будь-який з елементарних методів. Метод функціонує за принципом «розділяй та пануй»: елементи масиву діляться на дві частини, і кожна з них потім сортується окремо. Для цього обирають деякий елемент х, назвемо його розділовим. Мета полягає у розташуванні всіх менших за х елементів зліва від х, а всіх більших за х елементів справа від х. Поділивши масив, слід повторити процедуру сортування для кожної частини, потім - для частин цих частин і т. д., доки кожна з частин масиву не міститиме лише один елемент. Зауважимо, що у деяких модифікаціях методу Хоара розташування та значення розділового елемента можуть змінюватися під час розподілу елементів. Розглянемо одну з таких модифікацій.

11 Швидке сортування Алгоритм методу Хоара є рекурсивним і для його реалізації було б зручно застосувати рекурсивну процедуру. Параметрами цієї процедури будуть змінні left та right, що позначатимуть ліву та праву межу розглядуваної частини масиву. Розділовим елементом вважатимемо середній за номером елемент частини масиву і присвоїмо значення цього елемента змінній х. Рекурсивний виклик процедури для поділу лівого підмасиву на дві частини здійснюється в тому разі, якщо ліва межа підмасиву менша за індекс його середнього елемента, а для поділу правого підмасиву якщо права межа більша за індекс середнього елемента. Для поділу елементів на дві частини застосовуємо два цикли у середині циклу. На кожній ітерації зовнішнього циклу здійснюватиметься один обмін елементами між лівою та правою частинами. Внутрішні цикли (здійснюють перегляд масиву зліва та справа) призначені для знаходження чергової пари елементів, що мають бути переставлені. Зазначимо, що переставленим може бути і сам розділовий елемент, при цьому він може втратити властивість розділовості.

12 Сортування методом злиття У запропонованому Дж. фон Нейманом методі сортування злиттям, як і в методі Хоара, реалізовано принцип «розділяй та пануй». Масив ділиться навпіл, до кожної половини застосовується рекурсивно та сама процедура сортування злиттям, а відсортовані частини з'єднуються в один впорядкований масив. Отже, базовою операцією методу є злиття двох упорядкованих масивів в один. Ефективний спосіб виконання цієї операції полягає в тому, що елементи масивів порівнюються і за результатами порівняння в новий масив записується елемент або з першого, або з другого масиву. Один з масивів під час злиття може закінчитися раніше. В такому випадку елементи іншого масиву, які ще не були опрацьовані, слід додати до нового масиву. Час злиття упорядкованих масивів лінійно залежить від їх сумарної довжини. Враховуючи цей факт, неважко буде довести, що повне сортування методом злиття, як і сортування методом Хоара, потребує виконання (n log n) базових операцій над елементами масиву розмірності n. Задачу злиття двох масивів реалізуємо за допомогою процедури. Оскільки процедура злиття має бути застосована до різних підмасивів, то зручно було б передавати масив до процедури як параметр.

13 Завдання для лабораторної роботи 1). Впорядкувати за спаданням методом вставки ті елементи кожного рядка матриці, що розташовані між мінімальним та максимальним елементами.