Інформатика – Поглиблений рівень

Пригадаємо!

Завдання 1. Відсотуйте числа методом обміну (бульбашки): 23, 12, 34, 67, 31, 10.

Завдання 2. Відсотуйте числа методом вибору: 23, 12, 34, 67, 31, 10.

Завдання 3. Відсотуйте числа методом вставлення: 23, 12, 34, 67, 31, 10.

Прочитайте!

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

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

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

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

Приклад. Нехай дано масив цілих чисел: 12, 7, 15, 4, 11, 1, 9.

• Ділимо масив на дві частини, наприклад, так: перша частина 12, 7, 15, 4; друга частина 11, 1, 9.
• Упорядковуємо частини в порядку збільшення значень елементів: перша частина 4, 7, 12, 15; друга — 1, 9, 11.
• Вибираємо і порівнюємо елементи, розташовані на крайніх лівих позиціях (числа 4 і 1). Менше значення записуємо у ліву крайню позицію буфера.

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

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

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

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

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

На цьому процес сортування завершено.

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

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

Завдання для самостійного виконання

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