Menu

Merge Sort In Java - Program do implementacji MergeSort

  • Główny
  • Inny
  • Merge Sort In Java - Program do implementacji MergeSort

merge sort java program implement mergesort

W tym samouczku wyjaśniono, czym jest sortowanie przez scalanie w Javie, algorytm MergeSort, pseudokod, implementacja sortowania przez scalanie, przykłady sortowania iteracyjnego i rekurencyjnego:

Technika sortowania przez scalanie wykorzystuje strategię „Podziel i zwyciężaj”. W tej technice zbiór danych, który ma być sortowany, jest dzielony na mniejsze jednostki w celu posortowania.

=> Przeczytaj serię szkoleń Easy Java.

Połącz sortowanie w Javie

Czego się nauczysz:

Połącz sortowanie w Javie

Na przykład, jeśli tablica ma być posortowana przy użyciu scalania, wówczas tablica jest dzielona wokół jej środkowego elementu na dwie pod-tablice. Te dwie pod-tablice są dalej dzielone na mniejsze jednostki, aż mamy tylko 1 element na jednostkę.

Po zakończeniu podziału technika ta łączy poszczególne jednostki, porównując każdy element i sortując je podczas scalania. W ten sposób, zanim cała tablica zostanie scalona z powrotem, otrzymamy posortowaną tablicę.

W tym samouczku omówimy ogólnie wszystkie szczegóły tej techniki sortowania, w tym jej algorytm i pseudokody, a także implementację tej techniki w Javie.

Algorytm MergeSort w Javie

Poniżej znajduje się algorytm tej techniki.

# 1) Zadeklaruj tablicę myArray o długości N

#dwa) Sprawdź, czy N = 1, moja tablica jest już posortowana

# 3) Jeśli N jest większe niż 1,

  • ustaw po lewej = 0, po prawej = N-1
  • oblicz środek = (lewy + prawy) / 2
  • Wywołaj podprocedurę merge_sort (myArray, left, middle) => to sortuje pierwszą połowę tablicy
  • Wywołaj podprocedurę merge_sort (myArray, middle + 1, right) => to posortuje drugą połowę tablicy
  • Wywołaj procedurę scalania podprogramów (myArray, left, middle, right), aby scalić tablice posortowane w powyższych krokach.

# 4) Wyjście

Jak widać w krokach algorytmu, tablica jest podzielona na dwie w środku. Następnie rekurencyjnie sortujemy lewą połowę tablicy, a następnie prawą połowę. Gdy pojedynczo posortujemy obie połówki, zostaną one scalone w celu uzyskania posortowanej tablicy.

Pseudokod scalania sortowania

Zobaczmy pseudokod dla techniki Mergesort. Jak już wspomniano, ponieważ jest to technika „dziel i rządź”, przedstawimy procedury dzielenia zbioru danych, a następnie łączenia posortowanych zbiorów danych.

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

W powyższym pseudokodzie mamy dwie procedury tj. Mergesort i merge. Procedura Mergesort dzieli tablicę wejściową na pojedynczą tablicę, którą można łatwo posortować. Następnie wywołuje procedurę scalania.

Procedura scalania scala poszczególne tablice podrzędne i zwraca wynikową posortowaną tablicę. Po zapoznaniu się z algorytmem i pseudokodem dla sortowania przez scalanie, zilustrujmy teraz tę technikę na przykładzie.

ScalSortowanie ilustracji

Rozważ następującą tablicę, która ma zostać posortowana przy użyciu tej techniki.

Scalanie ilustracji sortowania

Teraz, zgodnie z algorytmem sortowania przez scalanie, podzielimy tę tablicę w jej środkowym elemencie na dwie pod-tablice. Następnie będziemy dalej dzielić tablice podrzędne na mniejsze tablice, aż otrzymamy pojedynczy element w każdej tablicy.

Gdy każda podtablica zawiera tylko jeden element, scalamy elementy. Podczas scalania porównujemy elementy i upewniamy się, że w scalonej tablicy są one uporządkowane. Dlatego pracujemy nad uzyskaniem scalonej tablicy, która jest posortowana.

Proces przedstawiono poniżej:

Scal proces sortowania

Jak pokazano na powyższej ilustracji, widzimy, że tablica jest wielokrotnie dzielona, ​​a następnie łączona, aby uzyskać posortowaną tablicę. Mając na uwadze tę koncepcję, przejdźmy do implementacji Mergesort w języku programowania Java.

Implementacja scalania sortowania w Javie

Możemy zaimplementować tę technikę w Javie używając dwóch podejść.

Iteracyjne sortowanie przez scalanie

Jest to podejście oddolne. Pod-tablice po jednym elemencie są sortowane i łączone w celu utworzenia dwuelementowych tablic. Te tablice są następnie łączone, tworząc czteroelementowe tablice i tak dalej. W ten sposób posortowana tablica jest budowana przez przejście w górę.

Poniższy przykład Java pokazuje iteracyjną technikę sortowania przez scalanie.

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)); } }

Wynik:

Oryginalna tablica: [10, 23, -11, 54, 2, 9, -10, 45]
Posortowana tablica: [-11, -10, 2, 9, 10, 23, 45, 54]

Iteracyjne sortowanie przez scalanie - wyjście

Rekurencyjne sortowanie przez scalanie

Jest to podejście odgórne. W tym podejściu tablica do posortowania jest dzielona na mniejsze tablice, aż każda tablica zawiera tylko jeden element. Wtedy sortowanie staje się łatwe do wykonania.

Poniższy kod Java implementuje rekurencyjne podejście techniki sortowania przez scalanie.

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

Wynik:

Oryginalna tablica: [10, 23, -11, 54, 2, 9, -10, 45]
Posortowana tablica: [- 11, -10, 2, 9, 10, 23, 45, 54]

Recursive MergeSort - wyjście

W następnej sekcji przełączmy się z tablic i użyjmy techniki do sortowania połączonych list i struktur danych list tablic.

Sortuj listę połączoną za pomocą sortowania przez scalanie w języku Java

Technika Mergesort jest najbardziej preferowana do sortowania połączonych list. Inne techniki sortowania działają słabo w przypadku listy połączonej ze względu na jej głównie sekwencyjny dostęp.

Poniższy program sortuje listę połączoną przy użyciu tej techniki.

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); } }

Wynik:

Oryginalna połączona lista:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Posortowana połączona lista:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

Wynik - Sortuj listę połączoną

Sortuj ArrayList za pomocą Merge Sort w Javie

Podobnie jak tablice i listy połączone, możemy również użyć tej techniki do sortowania ArrayList. Użyjemy podobnych procedur do rekurencyjnego podzielenia ArrayList, a następnie scalenia podlist.

Poniższy kod Java implementuje technikę sortowania Merge dla 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(); } }

Wynik:

Oryginalna lista ArrayList:
17 40 36 7 6 23 35 2 38
Sorted ArrayList:
2 6 7 17 23 35 36 38 40

Wyjście - Sortuj ArrayList

Często Zadawane Pytania

P # 1) Czy sortowanie przez scalanie można wykonać bez rekursji?

Odpowiedź: Tak. Możemy wykonać nierekurencyjne sortowanie według scalania, zwane „iteracyjnym sortowaniem scalającym”. Jest to podejście oddolne, które rozpoczyna się od scalenia tablic podrzędnych z jednym elementem w tablicę podrzędną złożoną z dwóch elementów.

Następnie te 2-elementowe tablice podrzędne są łączone w 4-elementowe tablice podrzędne i tak dalej przy użyciu konstrukcji iteracyjnych. Ten proces trwa do momentu, gdy mamy posortowaną tablicę.

Pytanie nr 2) Czy można przeprowadzić sortowanie przez scalanie na miejscu?

Odpowiedź: Sortowanie przez scalanie zazwyczaj nie jest lokalne. Ale możemy to zrobić, używając sprytnej implementacji. Na przykład, poprzez przechowywanie wartości dwóch elementów w jednej pozycji. Można to później wyodrębnić za pomocą modułu i dzielenia.

Pytanie 3) Co to jest 3 sposoby sortowania przez scalanie?

Odpowiedź: Technika, którą widzieliśmy powyżej, to dwukierunkowe sortowanie przez scalanie, w którym dzielimy tablicę do sortowania na dwie części. Następnie sortujemy i scalamy tablicę.

W 3-kierunkowym sortowaniu przez scalanie zamiast rozdzielać tablicę na 2 części, dzielimy ją na 3 części, a następnie sortujemy i na koniec łączymy.

Pytanie 4) Jaka jest złożoność czasowa Mergesort?

Odpowiedź: Całkowita złożoność czasowa sortowania przez scalanie we wszystkich przypadkach wynosi O (nlogn).

Pytanie nr 5) Gdzie jest używane sortowanie przez scalanie?

Odpowiedź: Jest używany głównie do sortowania połączonej listy w czasie O (nlogn). Jest również używany w scenariuszach rozproszonych, w których nowe dane trafiają do systemu przed lub po sortowaniu. Jest to również używane w różnych scenariuszach baz danych.

Wniosek

Sortowanie przez scalanie jest sortowaniem stabilnym i jest wykonywane przez najpierw wielokrotne dzielenie zestawu danych na podzbiory, a następnie sortowanie i scalanie tych podzbiorów w celu utworzenia posortowanego zestawu danych. Zestaw danych jest dzielony, aż każdy zestaw danych będzie prosty i łatwy do sortowania.

aplikacje umożliwiające pobieranie filmów z YouTube

Widzieliśmy rekurencyjne i iteracyjne podejście do techniki sortowania. Omówiliśmy również sortowanie struktury danych Linked List i ArrayList przy użyciu Mergesort.

Będziemy kontynuować dyskusję na temat innych technik sortowania w naszych nadchodzących samouczkach. Bądźcie czujni!

=> Odwiedź tutaj ekskluzywną serię samouczków szkoleniowych Java.

rekomendowane lektury

^