2018-01-08
311
1. Brian W. KernighanandDennis M. Ritchie «The C ProgrammingLanguage» (SecondEdition). — 1988. [ISBN 0–13–110362–8]
2. Donald E. Knuth «TheArtofComputerProgramming»: «Volume 3: SortingandSearching» (SecondEdition). — 1998. [ISBN 0–201–89685–0]
3. Donald L. Shell «A high-speedsortingprocedure» // Communicationsofthe ACM, Volume 2, Issue 7. — 1959. [ISSN 0001–0782]
Лабораторна робота № 4
Лабораторна робота № 4
Тема роботи: Метод сортування злиттям.
Мета роботи: Вивчити алгоритм сортування злиттям. Здійснити програмну реалізацію алгоритму сортування злиттям. Дослідити швидкодію алгоритму сортування злиттям.
Короткі теоретичні відомості
Сортування злиттям (англійською «MergeSort») — алгоритм сортування, в основі якого лежить принцип «розділяй та володарюй» (англійською «DivideandConquer»). В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.
Підчас сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.
Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається повернення з рекурсії. Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.
Час роботи алгоритму T (n) по впорядкуванню n елементів задовільняє рекурентному співвідношенню: T (n) = 2∙ T (½∙ n) + O (n), де T (½∙ n) — час на впорядкування половини масиву, O (n) — час на злиття цих половинок.
Враховуючи, що T (1) = O (1), розв’язком співвідношення є: T (n) = O (n ∙log(n)).
Крім того, алгоритм потребує для своєї роботи E (n) додаткової пам’яті.
Алгоритм не міняє порядок розташування однакових елементів, а отже він є стабільним.
Швидкість алгоритму є асимптотично оптимальною. Але її можна пришвидшити в константну кількість разів.Можливіоптимізаці:
· Оптимізація впорядкування невеликих частин масиву — невеликі частини масиву (наприклад, при n < 50) впорядковуватисортуванням вставкою.
· Оптимізація кількості копіювань елементів — при злитті двох впорядкованих масивів в один, кожен елемент копіюється два рази (спочатку у тимчасовий масив, а потім знову у початковий). Кількість копіювань можна зменшити удвічі, якщо по черзі використовувати для об’єднання початковий і тимчасовий масиви. Тоді можна не виконвати зайві операції копіювання.
