nvk 12 RIVNE - 36_Сортування злиттям та підрахунком

Урок 36_Сортування злиттям. Сотрування підрахунком.

Пригадаємо!
Відсортуйте масив чисел: 19, 36, 28, 95, 84, 7.

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

Припустимо, що є одновимірний масив цілих чисел завдовжки 20. Чи можна, на вашу думку, виконати його сортування, якщо спочатку виконати сортування перших 10 чисел, потім останніх 10 чисел? Як це можна зробити?

Сортування злиттям

Сортування злиттям належить до зовнішніх методів сортування. Він був створенний Джоном фон Нейманом у 1945 році та вважається одним із найпростіших алгоритмів серед швидких алгоритмів сортування. Розглянемо сутність алгоритму сортування масиву злиттям.

Розглянемо алгоритм сортування масиву злиттям на прикладі. Нехай дано масив цілих чисел: 12, 7, 15, 4, 11, 1, 9.

1. Ділимо масив на дві частини, наприклад, так: перша частина 12, 7, 15, 4; друга частина 11, 1, 9.

2. Упорядковуємо частини в порядку збільшення значень елементів: перша частина 4, 7, 12, 15; друга — 1, 9, 11.

3. Вибираємо і порівнюємо елементи, розташовані на крайніх лівих позиціях (числа 4 і 1). Менше значення записуємо у ліву крайню позицію буфера.

4. Зсуваємо другу частину масиву на одну позицію ліворуч. Порівнюємо числа 4 і 9. Число 4 записуємо у чергову позицію буфера.

5. Зсуваємо першу частину на одну позицію ліворуч. Порівнюємо числа 7 і 9. Число 7 записуємо у чергову позицію буфера.

6. Зсуваємо першу частину на одну позицію ліворуч. Порівнюємо числа 12 і 9. Число 9 записуємо у буфер.

7. Зсуваємо другу частину на одну позицію ліворуч. Порівнюємо числа 12 і 11. Число 11 записуємо у буфер.

8. Зсуваємо другу частину на одну позицію ліворуч. Оскільки друга частина стала порожньою, записуємо всі елементи, що залишилися у першій частині, у буфер без змін. На цьому процес сортування завершено.

Відзначимо, що алгоритм сортування злиттям для великих масивів є одним із найбільш швидкісних. Але він потребує додаткової пам’яті для збереження буферу, який за обсягом рівний обсягу початкового масиву.

На рис. 6.4 зображено програму сортування масиву злиттям:

Результат виконання програми:

Практичне завдання (виконайте самостійно)

Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.

Завдання 1. На основі здійснення аналізу програми (рис. 6.4) подайте у словесно-формульній формі алгоритм сортування масиву злиттям.

Нехай є масив цілих чисел завдовжки 10, елементи якого мають значення 0, 1, 2,3,4. Які особливості слід врахувати в процесі впорядкування такого масиву?

Сортування підрахунком

Метод сортування підрахунком застосовується тільки для масивів цілих чисел. Із точки зору швидкодії й необхідності використання додаткової пам’яті цей метод є ефективним для масивів, у яких зберігаються числа невеликого діапазону, особливо для чисел у діапазоні від 0 до 9.

Розглянемо сутність алгоритму сортування підрахунком на прикладі.

Дано початковий масив чисел, який потрібно відсортувати в порядку зростання значень його елементів:

2 0 0 1 5 3 1 2 0 3 0 1 2 1 0

1. Створимо додатковий порожній масив, довжина якого на одиницю більша від максимального значення елемента в початковому масиві (у наведеному масиві максимальним є число 5):

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

3. Початковий масив заповнюється новими значеннями, починаючи з нульової позиції. Оскільки перший елемент додаткового масиву має значення 5, то підряд записуються п’ять нулів, далі чотири одиниці і т. д. Якщо значення елемента додаткового масиву дорівнює 0, то відповідне число в масив не записується.

Один із найпростіших варіантів реалізації алгоритму сортування підрахунком зображено на рис. 6.5. Програма виконує сортування масиву цілих невід’ємних чисел (від 0 до 9) з максимальним значенням елемента не більше 9. Для сортування чисел із більшим діапазоном необхідно збільшити на потрібну величину розмір додаткового масиву, тобто внести зміни до третьої зверху інструкції: mas1 = [0, 0, ..., 0].

Результат виконання програми:

Зверніть увагу на те, що в початковому масиві відсутнє число 4. Але в додатковому масиві для нього відведено позицію, значення елемента якої дорівнює нулю. У програмі така ситуація врахована. Позиції додаткового масиву з нульовим значенням ігноруються, тому і число 4 у відсортований масив не виводиться.

Методи сортування найчастіше аналізуються за такими характеристиками:

• кількість порівнянь в ітерації;

• загальна кількість порівнянь;

• кількість ітерацій (переглядів).

Конкретні значення цих характеристик дозволяють вибрати оптимальний метод сортування для певного завдання. Значна кількість дослідників надають перевагу сортуванню методом обміну, оскільки він вимагає найменшої кількості обмінів.

Практичне завдання (виконайте самостійно)

Завдання 1. На основі здійснення аналізу програми (рис. 6.5) подайте у словесно-формульній формі алгоритм сортування масиву підрахунком.

Page updated

Google Sites

Report abuse