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

Сортування злиттям - це досить швидке сортування, час роботи якої О (n * log n). Однак її недоліком є той факт, що вона вимагає відносно багато пам'яті.

Основна ідея полягає в тому, що на кожному кроці ми розбиваємо масив на 2 рівні частини, сортуємо їх, а потім зливаємо два відсортованих шматка. Тобто виходить рекурсивне сортування - кожну з цих 2 частин ми будемо сортувати аналогічно. Вихід з рекурсії буде відбуватися тоді, коли у нас залишається менше 3 елементів. Якщо їх залишається всього 2, то міняємо їх між собою у міру потреби. Якщо залишається тільки 1 елемент, то залишаємо його в спокої.

Нехай дано вихідний масив з 7 елементів: 7 4 2 1 0 5 3

Крок 0: 7 4 2 1 0 5 3

Крок 1: 4 7 2 1 0 5 3

Крок 2: 4 7 1 2 0 5 3

Крок 3: 1 2 4 7 0 5 3

Крок 4: 1 2 4 7 0 3 5

Крок 5: 0 1 2 3 4 5 7

Розглянемо кожен крок докладно:

Крок 1: Спочатку рекурсія спуститься максимально глибоко, тобто до елементів a [0] і a [1]. Так як 7 > 4, то вони поміняються місцями.

Крок 2: Далі дивимося на елементи a [3] і a [4]. Так як вони теж стоять неправильно, то міняємо їх місцями.

Крок 3: Зараз крайніми є елементи з індексами 0 і 3. У нас є 2 відсортовані частини. Залишилося їх злити, щоб шматок від a [0] до a [3] став відсортованим. Для цього заведемо додатковий масив buf, куди будемо записувати мінімальний елемент з лівої і правої частини. Так як вони вже відсортовані, то будемо порівнювати самі ліві елементи. Так як 1 < 4, то в buf відправиться 1. Далі, з тих же міркувань в buf відправляється 2. Так як в правій частині елементи закінчилися, то в buf відправляються елементи 4 і 7. Тепер коли buf сформований, поміщаємо його вміст в масив a.

Крок 4: Аналогічно поступаємо з правою частиною, тобто з шматком масиву і індексами від 4 до 6.

Крок 5: Зливаємо ліву і праву частини. Отримуємо відсортований масив.

На рисунку. 3.1 представлений приклад методу сортування масиву.

На рисунку. 3.2 представлена блок-схема програми“Сортування методом злиття”

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

Порівняння методів сортування в загальному вигляді представлено в табл. 1, де приведено мінімальне, середнє та максимальне значення вказаних величин [4, 6–10].

Було проведено перевірку швидкодії комп’ютерних програм на основі відомих методів сортування. Час роботи різних програм сортування для масиву розмірністю n=256 представлено в табл. 2.

Висновок

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

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

В результаті перевірки відомих методів сортування на швидкодію з використанням масиву сталого об’єму було визначено час роботи програм сортування на основі різних методів. При цьому найкращі результати показали методи Шела та швидкого сортування.

На рисунку. 3.3 приклад виконання роботи програми“Сортування методом злиття”

Література

1. Лэнгсам, Й. Структуры данных для персональных ЭВМ [Текст] / Й. Лэнгсам, М. Огенстайн, А. Тененбаум. – М. : Мир, 1989. – 568 с.

2. Вышинский, В. А. Сортировка чисел в матрично-алгебраической ЭВМ [Текст] / В. А. Вышинский // Управляющие системы и машины. – 2001.

3. Лорин, Г. Сортировка и системы сортировки [Текст] / Г. Лорин. – М. : Мир, 1983. – 384 с.

4. Вирт, Н. Алгоритмы + структуры данных = программа [Текст] / Н. Вирт. – М. : Мир, 1985. – 406 с.

5. Программирование алгоритмов обработки данных [Текст] / О. В. Ускова, Н. В. Огаркова, И. Е. Воронина и др. –СПб. : БХВ-Петербург, 2003.

6. Гузик, В. Ф. Организация различныхметодов сортировки в вычислительных системах [Текст] / В. Ф. Гузик,

В. Е. Золотовский, С. А. Чиненков // Электронное моделирование. – 1992. – Т. 14, № З. – С. 25–28.

7. Hea, M. An optimal and processor efficient parallel sorting algorithm on a linear array with a reconfigurable pipelined bus system [Text] / M. Hea, X. Wua, S. Q. Zhengb // Computers & Electrical Engineering. –2009. – Vol. 35, Issue 6.

8. Sorting algorithms on transputer arrays [Text] / S. Chandra, M. Jain, A. Basu, P. S. Kumar // Parallel Computing. – 1993. – Vol. 19, Issue 6. – P. 595–607.

9. Lin, Y.-C. Parallel sorting with cooperating heaps in a linear array of processors [Text] / Yen-Chun Lin, Ferng-Ching Lin // Parallel Computing. – 1990. – Vol. 16, Issue 2–3. –P. 273–278.

10. Кнут, Д. Э. Искусство программ-мирования. Т. 3. Сортировка и поиск [Текст] / Д. Э. Кнут. – 2-е изд. – М. : Вильямс, 2003. – 832 с.