merge sort java program implement mergesort
Цей посібник пояснює, що таке сортування злиття в Java, алгоритм злиття сортування, псевдокод, реалізація сортування злиття, приклади ітеративного та рекурсивного злиття сортів:
Техніка сортування об’єднань використовує стратегію «Розділи і переможи». У цій техніці набір даних, що підлягає сортуванню, ділиться на менші одиниці для його сортування.
=> Прочитайте серію Easy Java Training.
Що ви дізнаєтесь:
- Об’єднати сортування на Java
- Висновок
Об’єднати сортування на Java
Наприклад, якщо масив потрібно сортувати за допомогою mergesort, то масив ділиться навколо свого середнього елемента на два підмасиви. Ці два підмасиви поділяються далі на менші одиниці, поки у нас не буде лише 1 елемент на одиницю.
Після закінчення поділу ця техніка об’єднує ці окремі одиниці шляхом порівняння кожного елемента та сортування при злитті. Таким чином, до того часу, коли весь масив буде об’єднаний назад, ми отримаємо відсортований масив.
У цьому підручнику ми обговоримо всі деталі цього методу сортування загалом, включаючи його алгоритм та псевдокоди, а також реалізацію методу на Java.
Алгоритм злиття в Java
Далі наведено алгоритм техніки.
# 1) Оголосити масив myArray довжиною N
# два) Перевірте, якщо N = 1, myArray вже відсортовано
# 3) Якщо N більше 1,
- встановити ліворуч = 0, праворуч = N-1
- обчислити середину = (ліворуч + праворуч) / 2
- Виклик підпрограми merge_sort (myArray, зліва, посередині) => це сортує першу половину масиву
- Виклик підпрограми merge_sort (myArray, middle + 1, right) => це відсортує другу половину масиву
- Викличте злиття підпрограми (myArray, ліворуч, посередині, праворуч), щоб об’єднати масиви, відсортовані за наведеними вище кроками.
# 4) Вихід
Як видно з кроків алгоритму, масив розділений на два посередині. Потім ми рекурсивно сортуємо ліву половину масиву, а потім праву половину. Як тільки ми окремо сортуємо обидві половинки, вони об’єднуються разом, щоб отримати відсортований масив.
Об’єднати сортувальний псевдокод
Давайте подивимось псевдокод для техніки Mergesort. Як уже обговорювалося, оскільки це техніка «поділи і переможи», ми представимо процедури розподілу набору даних, а потім злиття відсортованих наборів даних.
procedure mergesort( var intarray as array ) if ( n == 1 ) return intarray var lArray as array = intarray(0) ... intarray (n/2) var rArray as array = intarray (n/2+1) ... intarray (n) lArray = mergesort(lArray ) rArray = mergesort(rArray ) return merge(lArray, rArray ) end procedure procedure merge( var l_array as array, var r_array as array ) var result as array while (l_array and r_array have elements ) if (l_array (0) > r_array (0) ) add r_array (0) to the end of result remove r_array (0) from r_array else add l_array (0) to the end of result remove l_array (0) from l_array end if end while while (l_array has elements ) add l_array (0) to the end of result remove l_array (0) from l_array end while while (r_array has elements ) add r_array (0) to the end of result remove r_array (0) from r_array end while return result end procedureУ наведеному вище псевдокоді ми маємо дві процедури, тобто Mergesort та merge. Підпрограма Mergesort розділяє вхідний масив на окремий масив, який досить легко сортувати. Потім він викликає процедуру злиття.
Підпрограма злиття об'єднує окремі підмасиви та повертає отриманий відсортований масив. Побачивши алгоритм та псевдокод для сортування Merge, давайте проілюструємо цей метод на прикладі.
Ілюстрація MergeSort
Розглянемо наступний масив, який слід відсортувати за допомогою цієї техніки.
Тепер згідно з алгоритмом сортування Merge ми розділимо цей масив у його середньому елементі на два підмасиви. Потім ми продовжимо розбивати підмасиви на менші масиви, поки не отримаємо по одному елементу в кожному масиві.
Як тільки кожен підмасив містить лише один елемент, ми об’єднуємо елементи. Під час злиття ми порівнюємо елементи та переконуємось, що вони в порядку в об’єднаному масиві. Отже, ми працюємо над тим, щоб отримати об’єднаний масив, який сортується.
Процес показаний нижче:
Як показано на наведеній вище ілюстрації, ми бачимо, що масив ділиться неодноразово, а потім об'єднується, щоб отримати відсортований масив. З огляду на цю концепцію, перейдемо до реалізації Mergesort в мові програмування Java.
Реалізація злиття сортування в Java
Ми можемо реалізувати техніку в Java, використовуючи два підходи.
Ітеративне сортування злиття
Це підхід знизу вгору. Підмасиви кожного елемента сортуються та об'єднуються, утворюючи двоелементні масиви. Потім ці масиви об’єднуються, утворюючи чотириелементні масиви тощо. Таким чином відсортований масив будується, рухаючись вгору.
У наведеному нижче прикладі Java показано ітеративний метод сортування злиття.
import java.util.Arrays; class Main { // merge arrays : intArray(start...mid) and intArray(mid+1...end) public static void merge(int() intArray, int() temp, int start, int mid, int end) { int k = start, i = start, j = mid + 1; // traverse through elements of left and right arrays while (i <= mid && j <= end) { if (intArray(i) < intArray(j)) { temp(k++) = intArray(i++); } else { temp(k++) = intArray(j++); } } // Copy remaining elements while (i <= mid) { temp(k++) = intArray(i++); } // copy temp array back to the original array to reflect sorted order for (i = start; i <= end; i++) { intArray(i) = temp(i); } } // sorting intArray(low...high) using iterative approach public static void mergeSort(int() intArray) { int low = 0; int high = intArray.length - 1; // sort array intArray() using temporary array temp int() temp = Arrays.copyOf(intArray, intArray.length); // divide the array into blocks of size m // m = (1, 2, 4, 8, 16...) for (int m = 1; m <= high - low; m = 2*m) { for (int i = low; i < high; i += 2*m) { int start = i; int mid = i + m - 1; int end = Integer.min(i + 2 * m - 1, high); //call merge routine to merge the arrays merge(intArray, temp, start, mid, end); } } } public static void main(String() args) { //define array to be sorted int() intArray = { 10,23,-11,54,2,9,-10,45 }; //print the original array System.out.println('Original Array : ' + Arrays.toString(intArray)); //call mergeSort routine mergeSort(intArray); //print the sorted array System.out.println('Sorted Array : ' + Arrays.toString(intArray)); } }Вихід:
Оригінальний масив: (10, 23, -11, 54, 2, 9, -10, 45)
Відсортований масив: (-11, -10, 2, 9, 10, 23, 45, 54)
Сортування рекурсивного злиття
Це підхід зверху вниз. При такому підході масив, що підлягає сортуванню, розбивається на менші масиви, поки кожен масив не містить лише одного елемента. Тоді сортування стає легким у здійсненні.
Наступний код Java реалізує рекурсивний підхід техніки сортування Merge.
import java.util.Arrays; public class Main { public static void merge_Sort(int() numArray) { //return if array is empty if(numArray == null) { return; } if(numArray.length > 1) { int mid = numArray.length / 2; //find mid of the array // left half of the array int() left = new int(mid); for(int i = 0; i Вихід:
Оригінальний масив: (10, 23, -11, 54, 2, 9, -10, 45)
Відсортований масив: (- 11, -10, 2, 9, 10, 23, 45, 54)
У наступному розділі давайте перейдемо від масивів і використаємо техніку для сортування пов’язаних списків та структур даних списку масивів.
Сортувати зв’язаний список за допомогою об’єднання Сортувати в Java
Техніка злиття є найбільш переважною для сортування пов'язаних списків. Інші методи сортування мають низьку ефективність, коли мова йде про зв’язаний список, через його переважно послідовний доступ.
Наступна програма сортує зв’язаний список за допомогою цієї техніки.
import java.util.*; // A singly linked list node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } }; class Main { //two sorted linked list are merged together to form one sorted linked list public static Node Sorted_MergeSort(Node node1, Node node2) { //return other list if one is null if (node1 == null) return node2; else if (node2 == null) return node1; Node result; // Pick either node1 or node2, and recur if (node1.data <= node2.data) { result = node1; result.next = Sorted_MergeSort(node1.next, node2); } else { result = node2; result.next = Sorted_MergeSort(node1, node2.next); } return result; } //splits the given linked list into two halves public static Node() FrontBackSplit(Node source) { // empty list if (source == null || source.next == null) { return new Node(){ source, null } ; } Node slow_ptr = source; Node fast_ptr = source.next; // Advance 'fast' two nodes, and advance 'slow' one node while (fast_ptr != null) { fast_ptr = fast_ptr.next; if (fast_ptr != null) { slow_ptr = slow_ptr.next; fast_ptr = fast_ptr.next; } } // split the list at slow_ptr just before mid Node() l_list = new Node(){ source, slow_ptr.next }; slow_ptr.next = null; return l_list; } // use Merge sort technique to sort the linked list public static Node Merge_Sort(Node head) { // list is empty or has single node if (head == null || head.next == null) { return head; } // Split head into 'left' and 'right' sublists Node() l_list = FrontBackSplit(head); Node left = l_list(0); Node right = l_list(1); // Recursively sort the sublists left = Merge_Sort(left); right = Merge_Sort(right); // merge the sorted sublists return Sorted_MergeSort(left, right); } // function to print nodes of given linked list public static void printNode(Node head) { Node node_ptr = head; while (node_ptr != null) { System.out.print(node_ptr.data + ' -> '); node_ptr = node_ptr.next; } System.out.println('null'); } public static void main(String() args) { // input linked list int() l_list = { 4,1,6,2,7,3,8 }; Node head = null; for (int key: l_list) { head = new Node(key, head); } //print the original list System.out.println('Original Linked List: '); printNode(head); // sort the list head = Merge_Sort(head); // print the sorted list System.out.println('
Sorted Linked List:'); printNode(head); } } Вихід:
Оригінальний зв’язаний список:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> нуль
Відсортований зв’язаний список:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> нуль
як викликати масив з іншого методу в Java
Сортування ArrayList за допомогою об’єднання сортування в Java
Як і списки масивів та зв’язок, ми також можемо використовувати цей прийом для сортування списку масивів. Ми використовуватимемо подібні процедури, щоб розділити ArrayList рекурсивно, а потім об’єднати підсписки.
Наведений нижче код Java реалізує техніку сортування Merge для ArrayList.
import java.util.ArrayList; class Main { //splits arrayList into sub lists. public static void merge_Sort(ArrayList numList){ int mid; ArrayList left = new ArrayList<>(); ArrayList right = new ArrayList<>(); if (numList.size() > 1) { mid = numList.size() / 2; // left sublist for (int i = 0; i numList, ArrayList left, ArrayList right){ //temporary arraylist to build the merged list ArrayList temp = new ArrayList<>(); //initial indices for lists int numbersIndex = 0; int leftIndex = 0; int rightIndex = 0; //traverse left and righ lists for merging while (leftIndex = left.size()) { temp = right; tempIndex = rightIndex; } else { temp = left; tempIndex = leftIndex; } for (int i = tempIndex; i numList = new ArrayList<>(); int temp; //populate the ArrayList with random numbers for (int i = 1; i <= 9; i++) numList.add( (int)(Math.random() * 50 + 1) ); //print original ArrayList of random numbers System.out.println('Original ArrayList:'); for(int val: numList) System.out.print(val + ' '); //call merge_Sort routine merge_Sort(numList); //print the sorted ArrayList System.out.println('
Sorted ArrayList:'); for(int ele: numList) System.out.print(ele + ' '); System.out.println(); } } Вихід:
Оригінальний список масивів:
17 40 36 7 6 23 35 2 38
Сортований ArrayList:
2 6 7 17 23 35 36 38 40
Часті запитання
Q # 1) Чи можна сортувати злиття без рекурсії?
Відповідь: Так. Ми можемо виконати нерекурсивне сортування злиття, яке називається «ітеративне сортування об’єднання». Це підхід знизу вгору, який починається об’єднанням підмасивів з одним елементом у підмасив із двох елементів.
Потім ці 2-елементні підмасиви об'єднуються в 4-елементні підмасиви тощо, використовуючи ітеративні конструкції. Цей процес триває, поки у нас не буде відсортований масив.
Q # 2) Чи можна зробити сортування об’єднанням на місці?
Відповідь: Сортування злиття зазвичай не відбувається. Але ми можемо зробити це на місці, використовуючи розумну реалізацію. Наприклад, зберігаючи значення двох елементів в одній позиції. Це можна отримати потім, використовуючи модуль і ділення.
Q # 3) Що таке три способи сортування?
Відповідь: Методика, яку ми бачили вище, - це двостороння сортування злиттям, при якій ми розділяємо масив, щоб сортувати його на дві частини. Потім сортуємо і об’єднуємо масив.
У 3-сторонньому сортуванні Merge замість того, щоб розділити масив на 2 частини, ми розділяємо його на 3 частини, потім сортуємо і, нарешті, об’єднуємо.
Q # 4) Яка часова складність Mergesort?
Відповідь: Загальна часова складність сортування Merge у всіх випадках дорівнює O (nlogn).
Q # 5) Де використовується сортування Merge?
Відповідь: Він в основному використовується для сортування пов'язаного списку за час O (nlogn). Він також використовується в розподілених сценаріях, коли нові дані надходять у систему до сортування або після нього. Це також використовується в різних сценаріях баз даних.
Висновок
Сортування злиття є стабільним сортуванням і виконується шляхом спочатку багаторазового розбиття набору даних на підмножини, а потім сортування та об'єднання цих підмножин для формування відсортованого набору даних. Набір даних розділяється, доки кожен набір даних не є тривіальним та легким для сортування.
Ми бачили рекурсивний та ітераційний підходи до техніки сортування. Ми також обговорили сортування структури даних Linked List та ArrayList за допомогою Mergesort.
Ми продовжимо обговорення інших методів сортування в наших майбутніх підручниках. Залишайтеся з нами!
=> Завітайте сюди, щоб ознайомитись із ексклюзивними навчальними посібниками з Java.
Рекомендована література
- Об’єднати сортування в C ++ із прикладами
- Як відсортувати масив на Java - Підручник з прикладами
- Сортування бульбашок на Java - алгоритми сортування Java та приклади коду
- Сортування виділення в Java - Алгоритм сортування виділення та приклади
- Сортування вставки на Java - Алгоритм сортування вставки та приклади
- Швидке сортування в Java - алгоритм, ілюстрація та реалізація
- Масиви в Java 8 - клас потоку та метод ParallelSort
- Вступ до методів сортування в C ++
