Сортування злиттям - Студопедія

Сортування злиттям(англ. merge sort)[1] є простим, але ефективним алгоритмом сортування, який так само як і алгоритм швидкого сортування побудований за принципом «розділяй і владарюй», проте реалізує його дещо по-іншому. Масив ділиться навпіл, ліва і права половина рекурсивно сортується тим самим методом злиття, потім відсортовані частини поєднуються в один відсортований масив. Відповідно до алгоритму розподіл продовжується до частини масиву, що складається з одного елемента. Такий масив відразу є відсортованим, тому завдання зводиться до написання методу, який виконує злиття двох відсортованих частин масиву один.

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

Завдання 6.7Напишіть рекурсивний метод сортування злиттям цілісного масиву.

Пояснення:у програмі використовуються такі методи:

mergeSort(int[] arr) – виконує сортування масиву arr[], викликаючи при цьому метод mergeSort(int[] arr, int low, int high, int[] buff);

mergeSort(int[] arr, int low, int high, int[] buff) – виконує сортування масиву arr[] від індексу low доіндексу high. Як аргумент метод передається допоміжний буфер buff[]. Метод здійснює рекурсивний поділ масиву навпіл і виклик методу злиття merge().

merge(int[]arr, int low, int high, int mid, int[] buff) – метод виконує злиття відсортованих частин масиву: лівої від ідекса low до mid і правою від індексу mid+1 до індексу high.

Приклад виконання алгоритму сортування злиттям масиву ілюструє рис. 6.5.

public class MergeSort

static void mergeSort(int[] arr)

mergeSort(arr, 0, arr.length - 1, новий int [arr.length]);

static void mergeSort(int[] arr, int low, int high, int[] buff)

mergeSort(arr, low, mid, buff);

mergeSort(arr, mid+1, high, buff);

//Викликаємо метод злиття

merge (arr, low, high, mid, buff);

static void merge (int [] arr, int low, int high, int mid, int [] buff)

int left = low, right = mid + 1;

for (int i = low; i highleft

//Копіюємо буфер в масив arr

for (int i = low; i

Чи не знайшли те, що шукали? Скористайтеся пошуком:

Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно

---