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

У запропонованому Дж. фон Нейманом методі сортування злиттям, як і в методі Хоара, реалізовано принцип «розділяй та пануй». Масив ділиться навпіл, до кож­ної половини застосовується рекурсивно та сама процедура сортування злиттям, а відсортовані частини з'єднуються в один впорядкований масив (рис. 6.1).

Рис. 6.1. Схема сортування методом злиття

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

Час злиття упорядкованих масивів лінійно залежить від їх сумарної довжини. Враховуючи цей факт, неважко буде довести, що повне сортування методом злиття, як і сортування методом Хоара, потребує виконання 0(п log п) базових операцій над елементами масиву розмірності п.

Хід роботи:

2. Вивчити теоретичний матеріал.

3. Виконати індивідуальне завдання.

4. Скласти звіт, в якому відповісти на теоретичні питання, описати алгоритм, описати програму, привести контрольний приклад виконання програми.

Контрольні запитання:

1. Які методи впорядкування масивів Ви знаєте?

2. Що таке метод обміну впорядкування масиву?

3. Що таке метод бульбашки?

4. Як оптимізувати метод бульбашки?

5. Яка робоча функція алгоритму бульбашки?

6. Що таке алгоритм включення для сортування масиву?

7. Що таке метод вибору сортування масиву?

8. Який метод називають методом швидкого сортування?

9. Яка робоча функція методу швидкого сортування?

Індивідуальні завдання: Скласти алгоритм та програму для розвязання задачі: Задано одномірний масив.

1. Впорядкувати його другу половину по спаданню непарних елементів.

2. Впорядкувати його першу половину по зростанню елементів з парними індексами.

3. Впорядкувати останні k елементів по спаданню значень парних елементів.

4. Впорядкувати елементи, розташовані до першого від'ємного елемента в порядку зростання елементів.

5. Впорядкувати елементи, розташовані після максимального елемента по спаданню значень елементів.

6. Впорядкувати елементи, розташовані між першим і останнім від'ємним елементом по зростанню значень елементів.

7. Впорядкувати елементи, розташовані між мінімальним і максимальними елементами по спаданню значень елементів.

8. Впорядкувати елементи, розташовані до мінімального елемента по зростанню значень елементів.

9. Впорядкувати елементи, розташовані після мінімального елементам по спаданню значень елементів.

10. Впорядкувати елементи, розташовані до максимального елементам по зростанню значень елементів.

11. Впорядкувати елементи, розташовані між першими і другими додатніми елементами по спаданню значень елементів.

12. Впорядкувати перші k парних елементів по спаданню значень елементів.

13. Впорядкувати тільки додатні елементи по зростанню.

14. Впорядкувати тільки ті елементи, що більше заданого n по зростанню.

15. Впорядкувати тільки елементи з непарними індексами по спаданню.