Menu

Sloučit řazení v Javě - program implementující MergeSort

  • Hlavní
  • Jiný
  • Sloučit řazení v Javě - program implementující MergeSort

merge sort java program implement mergesort

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Tento výukový program vysvětluje, co je Sloučit řazení v Javě, Algoritmus MergeSort, Pseudokód, Implementace Sloučit řazení, Příklady Iterativního a rekurzivního MergeSortu:

Technika sloučení používá strategii „Rozděl a panuj“. V této technice je datová sada, která má být tříděna, rozdělena na menší jednotky, aby se setřídila.

=> Přečtěte si řadu Easy Java Training Series.

Sloučit řazení v Javě

Co se naučíte:

Sloučit řazení v Javě

Například, pokud má být pole tříděno pomocí mergesortu, je pole rozděleno kolem středního prvku do dvou dílčích polí. Tato dvě dílčí pole jsou dále rozdělena na menší jednotky, dokud nebudeme mít pouze 1 prvek na jednotku.

Jakmile je rozdělení hotové, tato technika sloučí tyto jednotlivé jednotky porovnáním každého prvku a jejich seřazením při slučování. Tímto způsobem v době, kdy je celé pole sloučeno zpět, získáme tříděné pole.

V tomto tutoriálu se budeme zabývat všemi podrobnostmi této techniky třídění obecně, včetně jejího algoritmu a pseudokódů, jakož i implementace této techniky v Javě.

Algoritmus MergeSort v Javě

Následuje algoritmus této techniky.

# 1) Deklarujte pole myArray o délce N

#dva) Zkontrolujte, zda je N = 1, myArray je již tříděno

# 3) Pokud je N větší než 1,

  • nastavení vlevo = 0, vpravo = N-1
  • vypočítat prostřední = (levý + pravý) / 2
  • Volejte podprogram merge_sort (myArray, vlevo, uprostřed) => toto seřadí první polovinu pole
  • Zavolejte podprogram merge_sort (myArray, prostřední + 1, pravý) => toto seřadí druhou polovinu pole
  • Voláním sloučení podprogramů (myArray, vlevo, uprostřed, vpravo) sloučíte pole seřazená podle výše uvedených kroků.

# 4) Výstup

Jak je vidět v krocích algoritmu, pole je rozděleno na dvě uprostřed. Potom rekurzivně roztřídíme levou polovinu pole a poté pravou polovinu. Jakmile obě poloviny jednotlivě roztřídíme, spojí se dohromady a získá se seřazené pole.

Sloučit pseudo kód řazení

Podívejme se na pseudokód pro techniku ​​Mergesort. Jak již bylo diskutováno, protože se jedná o techniku ​​„rozděl a panuj“, představíme rutiny pro rozdělení datové sady a následné sloučení seřazených datových sad.

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

Ve výše uvedeném pseudokódu máme dvě rutiny, tj. Mergesort a sloučení. Rutina Mergesort rozděluje vstupní pole na individuální pole, které lze snadno seřadit. Pak zavolá slučovací rutinu.

Rutina sloučení sloučí jednotlivá dílčí pole a vrátí výsledné seřazené pole. Poté, co jsme viděli algoritmus a pseudokód pro třídění sloučení, pojďme nyní ilustrovat tuto techniku ​​na příkladu.

MergeSort ilustrace

Zvažte následující pole, které má být tříděno pomocí této techniky.

Sloučit řazení obrázku

Nyní podle algoritmu Merge sort rozdělíme toto pole v jeho středním prvku na dvě dílčí pole. Pak budeme pokračovat v dělení dílčích polí na menší pole, dokud nezískáme v každém poli jeden prvek.

Jakmile má každé dílčí pole pouze jeden prvek, spojíme je. Při slučování porovnáváme prvky a zajišťujeme, aby byly ve sloučeném poli v pořádku. Postupně tedy postupujeme nahoru, abychom získali sloučené pole, které je tříděno.

Proces je uveden níže:

Sloučit proces třídění

Jak je znázorněno na výše uvedeném obrázku, vidíme, že pole je opakovaně rozděleno a poté sloučeno, aby se získalo seřazené pole. S ohledem na tento koncept pojďme k implementaci Mergesortu v programovacím jazyce Java.

Sloučit implementaci řazení v Javě

Můžeme implementovat techniku ​​v Javě pomocí dvou přístupů.

Iterativní sloučení řazení

Jedná se o přístup zdola nahoru. Podadresy jednoho prvku jsou každý tříděny a sloučeny, aby vytvořily pole dvou elementů. Tato pole se poté sloučí a vytvoří pole se čtyřmi prvky atd. Tímto způsobem je seřazené pole vytvořeno směrem nahoru.

Níže uvedený příklad Java ukazuje iterační techniku ​​Merge Sort.

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

Výstup:

Původní pole: (10, 23, -11, 54, 2, 9, -10, 45)
Řazené pole: (-11, -10, 2, 9, 10, 23, 45, 54)

Iterativní sloučení - výstup

Rekurzivní sloučení řazení

Jedná se o přístup shora dolů. V tomto přístupu je pole, které má být tříděno, rozděleno na menší pole, dokud každé pole neobsahuje pouze jeden prvek. Pak se třídění stane snadno implementovatelným.

Následující kód Java implementuje rekurzivní přístup techniky řazení 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

Výstup:

Původní pole: (10, 23, -11, 54, 2, 9, -10, 45)
Řaděné pole: (- 11, -10, 2, 9, 10, 23, 45, 54)

Rekurzivní MergeSort - výstup

V další části pojďme přepnout z polí a pomocí této techniky třídit datové struktury propojeného seznamu a seznamu polí.

Seřadit propojený seznam pomocí Sloučit Seřadit v Javě

Pro třídění propojených seznamů je nejpreferovanější technika spojování. Jiné techniky třídění fungují špatně, pokud jde o propojený seznam kvůli jeho převážně sekvenčnímu přístupu.

Následující program třídí propojený seznam pomocí této techniky.

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

Výstup:

Původní propojený seznam:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Seřazený propojený seznam:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

nejlepší servery pro hraní na wow

Výstup - seřazení propojeného seznamu

Seřadit ArrayList pomocí Sloučit Seřadit v Javě

Stejně jako pole a propojené seznamy můžeme tuto techniku ​​použít i pro třídění ArrayList. Podobné rutiny použijeme k rekurzivnímu rozdělení ArrayList a následnému sloučení sublistů.

Níže uvedený kód Java implementuje techniku ​​třídění sloučení pro 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(); } }

Výstup:

Original ArrayList:
17 40 36 7 6 23 35 2 38
Seřazené ArrayList:
2 6 7 17 23 35 36 38 40

Výstup - řazení ArrayList

Často kladené otázky

Otázka č. 1) Lze sloučení třídit bez rekurze?

Odpovědět: Ano. Můžeme provést nerekurzivní sloučení, které se nazývá iterativní sloučení. Jedná se o přístup zdola nahoru, který začíná sloučením dílčích polí s jedním prvkem do dílčího pole dvou prvků.

Pak jsou tato 2prvková dílčí pole sloučena do 4prvkových dílčích polí atd. Pomocí iterativních konstrukcí. Tento proces pokračuje, dokud nebudeme mít seřazené pole.

Otázka č. 2) Lze sloučení třídit na místě?

Odpovědět: Sloučení není obecně na místě. Ale můžeme to udělat na místě pomocí nějaké chytré implementace. Například, uložením hodnoty dvou prvků na jednu pozici. To lze následně extrahovat pomocí modulu a dělení.

Otázka č. 3) Co je třícestné sloučení?

Odpovědět: Technika, kterou jsme viděli výše, je 2-way Merge sort, kde jsme rozdělili pole, které se má třídit, na dvě části. Potom pole roztřídíme a sloučíme.

Ve třícestném sloučení namísto rozdělení pole na 2 části rozdělíme na 3 části, poté je roztřídíme a nakonec sloučíme.

Otázka č. 4) Jaká je časová složitost Mergesortu?

Odpovědět: Celková časová složitost sloučení je ve všech případech O (nlogn).

Otázka č. 5) Kde se používá druh sloučení?

Odpovědět: Většinou se používá při třídění propojeného seznamu v čase O (nlogn). Používá se také v distribuovaných scénářích, kdy nová data přicházejí do systému před nebo po třídění. To se také používá v různých databázových scénářích.

Závěr

Sloučit sloučení je stabilní řazení a provádí se tak, že se nejprve datová sada opakovaně rozdělí na podmnožiny a poté seřadí a sloučí tyto podmnožiny, aby se vytvořila seřazená datová sada. Datová sada je rozdělena, dokud není každá datová sada triviální a snadno seřizuje.

Viděli jsme rekurzivní a iterativní přístupy k technice třídění. Také jsme diskutovali o třídění datové struktury Propojený seznam a ArrayList pomocí Mergesortu.

Budeme pokračovat v diskusi o dalších technikách třídění v našich připravovaných tutoriálech. Zůstaňte naladěni!

=> Navštivte zde exkluzivní sérii výukových programů Java.

Doporučené čtení

^