Menu

Zlúčiť Zoradiť v Jave - program na implementáciu MergeSort

  • Hlavná
  • Iné
  • Zlúčiť Zoradiť v Jave - program na implementáciu MergeSort

merge sort java program implement mergesort

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento výukový program vysvetľuje, čo je zlúčenie zoradenia v Jave, algoritmus MergeSort, pseudokód, implementácia zlúčenia zoradenia, príklady iteračného a rekurzívneho zlúčenia:

Technika zlúčenia využíva stratégiu „Rozdeľuj a panuj“. V tejto technike je súbor údajov, ktorý sa má triediť, rozdelený na menšie jednotky, aby sa zoradil.

=> Prečítajte si sériu Easy Java Training Series.

Zlúčiť zoradenie v Jave

Čo sa dozviete:

Zlúčiť zoradenie v Jave

Napríklad, ak sa má pole zoradiť pomocou mergesortu, potom je pole rozdelené okolo jeho stredného prvku do dvoch čiastkových polí. Tieto dve čiastkové polia sa ďalej delia na menšie jednotky, až kým nebudeme mať iba 1 prvok na jednotku.

Po dokončení rozdelenia táto technika zlúči tieto jednotlivé jednotky porovnaním každého prvku a ich triedením pri zlučovaní. Takto v čase, keď je celé pole zlúčené späť, získame zoradené pole.

V tomto výučbe sa budeme venovať všetkým podrobnostiam tejto techniky triedenia všeobecne, vrátane ich algoritmov a pseudokódov, ako aj implementácii tejto techniky v prostredí Java.

Algoritmus MergeSort v Jave

Nasleduje algoritmus tejto techniky.

# 1) Vyhláste pole myArray dĺžky N

#dva) Skontrolujte, či je N = 1, myArray je už zoradený

# 3) Ak N je väčšie ako 1,

  • vľavo = 0, vpravo = N-1
  • vypočítať stred = (vľavo + vpravo) / 2
  • Zavolajte podprogram merge_sort (myArray, ľavý, stredný) => takto sa zoradí prvá polovica poľa
  • Zavolajte podprogram merge_sort (myArray, stredný + 1, pravý) => toto roztriedi druhú polovicu poľa
  • Zavolajte zlúčenie podprogramov (myArray, ľavé, stredné, pravé), aby ste zlúčili polia zoradené podľa vyššie uvedených krokov.

# 4) Východ

Ako je vidieť v krokoch algoritmu, pole je rozdelené na dve uprostred. Potom rekurzívne triedime ľavú polovicu poľa a potom pravú polovicu. Keď obidve polovice jednotlivo zoradíme, spoja sa a vznikne zoradené pole.

Zlúčiť pseudo kód

Pozrime sa na pseudokód techniky Mergesort. Ako už bolo uvedené, pretože ide o techniku ​​„rozdeľuj a panuj“, predstavíme postupy na rozdelenie množiny údajov a následné zlúčenie zoradených množín údajov.

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

Vo vyššie uvedenom pseudo-kóde máme dve rutiny, tj. Mergesort a zlúčenie. Rutina Mergesort rozdelí vstupné pole na samostatné pole, ktoré je ľahké na zoradenie. Potom zavolá zlučovaciu rutinu.

Rutina zlúčenia zlúči jednotlivé čiastkové polia a vráti výsledné zoradené pole. Po zobrazení algoritmu a pseudokódu pre triedenie zlúčenia si teraz ukážeme túto techniku ​​na príklade.

Ilustrácia MergeSort

Zvážte nasledujúce pole, ktoré sa má triediť pomocou tejto techniky.

Zlúčiť ilustráciu zoradenia

Teraz podľa algoritmu Merge sort rozdelíme toto pole v jeho strednom prvku do dvoch podradených polí. Potom budeme pokračovať v delení čiastkových polí na menšie polia, kým v každom poli nezískame jeden prvok.

Keď má každé podpole iba jeden prvok, zlúčime ich. Pri zlučovaní porovnávame prvky a zabezpečujeme ich usporiadanie v zlúčenom poli. Takže sa prepracujeme k získaniu zlúčeného poľa, ktoré je zoradené.

Postup je uvedený nižšie:

Zlúčiť proces triedenia

Ako je znázornené na vyššie uvedenom obrázku, vidíme, že pole je opakovane rozdelené a potom zlúčené, aby sa získalo zoradené pole. S ohľadom na tento koncept poďme k implementácii Mergesortu v programovacom jazyku Java.

Zlúčiť implementáciu triedenia v Jave

Techniku ​​môžeme implementovať v Jave pomocou dvoch prístupov.

Iteratívne zlúčenie zoradiť

Toto je prístup zdola nahor. Podradené polia po jednom prvku sú zoradené a zlúčené, aby vytvorili dvojprvkové polia. Tieto polia sa potom zlúčia a vytvoria sa štvorprvkové polia atď. Týmto spôsobom je zoradené pole zostavené smerom nahor.

Nasledujúci príklad Javy 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ýkon:

Originálne pole: (10, 23, -11, 54, 2, 9, -10, 45)
Zoradené pole: (-11, -10, 2, 9, 10, 23, 45, 54)

Iteratívne zlúčenie - výstup

Rekurzívne zlúčenie

Toto je prístup zhora nadol. V tomto prístupe je pole, ktoré sa má triediť, rozdelené na menšie polia, kým každé pole neobsahuje iba jeden prvok. Potom sa triedenie stane ľahko implementovateľným.

Nasledujúci kód Java implementuje rekurzívny prístup techniky triedenia Zlúčenie.

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ýkon:

Originálne pole: (10, 23, -11, 54, 2, 9, -10, 45)
Zoradené pole: (- 11, -10, 2, 9, 10, 23, 45, 54)

Rekurzívny MergeSort - výstup

V ďalšej časti poďme prejsť na pole a pomocou tejto techniky zoradiť dátové štruktúry prepojeného zoznamu a zoznamu polí.

Zoradiť prepojený zoznam pomocou Zlúčiť Zoradiť v Jave

Na triedenie prepojených zoznamov je najpreferovanejšou technika spájania. Ostatné techniky triedenia majú slabý výkon, pokiaľ ide o prepojený zoznam, pretože majú väčšinou sekvenčný prístup.

Nasledujúci program triedi prepojený zoznam pomocou tejto 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ýkon:

Pôvodný prepojený zoznam:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nulové
Zoradený prepojený zoznam:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nulové

ako zavolať pole z inej metódy v jave -

Výstup - zoradenie prepojeného zoznamu

Zoradiť ArrayList pomocou Zlúčiť Zoradiť v Jave

Rovnako ako polia a prepojené zoznamy, aj túto techniku ​​môžeme použiť na triedenie ArrayList. Podobné rutiny použijeme na to, aby sme ArrayList rekurzívne rozdelili a potom zlúčili podzoznamy.

Nižšie uvedený kód Java implementuje techniku ​​zoradenia zlúčenia pre 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ýkon:

Originálny zoznam polí:
17 40 36 7 6 23 35 2 38
Zoradený zoznam polí:
2 6 7 17 23 35 36 38 40

Výstup - zoradenie ArrayList

často kladené otázky

Otázka 1) Je možné zlúčenie zoradiť bez rekurzie?

Odpoveď: Áno. Môžeme vykonať nerekurzívne zlúčenie, ktoré sa nazýva „iteratívne zlúčenie“. Toto je prístup zdola nahor, ktorý začína zlúčením čiastkových polí s jedným prvkom do podskupiny dvoch prvkov.

Potom sa tieto 2-prvkové čiastkové polia zlúčia do 4-prvkových čiastkových polí atď. Pomocou iteratívnych konštruktov. Tento proces pokračuje, kým nebudeme mať zoradené pole.

Otázka č. 2) Je možné zlúčiť triedenie na mieste?

Odpoveď: Zlúčenie sa zvyčajne nenachádza na danom mieste. Ale dokážeme to vyrobiť na mieste pomocou nejakej šikovnej implementácie. Napríklad, uložením hodnoty dvoch prvkov na jednu pozíciu. Toto je možné extrahovať potom pomocou modulu a rozdelenia.

Otázka č. 3) Čo je 3-stupňové zlúčenie?

Odpoveď: Technika, ktorú sme videli vyššie, je 2-cestné zlúčenie, pri ktorom sme rozdelili pole, ktoré sa má zoradiť, na dve časti. Potom zoradíme a zlúčime pole.

Pri trojcestnom zlúčení namiesto rozdelenia poľa na 2 časti ho rozdelíme na 3 časti, potom ho roztriedime a nakoniec zlúčime.

Otázka č. 4) Aká je časová náročnosť Mergesortu?

Odpoveď: Celková časová zložitosť zlúčenia je vo všetkých prípadoch O (nlogn).

Otázka č. 5) Kde sa používa druh zlúčenia?

Odpoveď: Väčšinou sa používa na triedenie prepojeného zoznamu v čase O (nlogn). Používa sa tiež v distribuovaných scenároch, keď do systému prichádzajú nové dáta pred alebo po triedení. Používa sa to aj v rôznych databázových scenároch.

Záver

Zlúčiť triedenie je stabilné triedenie a vykonáva sa tak, že sa najskôr množina údajov opakovane rozdelí na podmnožiny a potom sa tieto podmnožiny roztriedia a zlúčia, čím sa vytvorí zoradená množina údajov. Množina údajov je rozdelená, až kým nie je každá množina údajov triviálna a ľahko sa triedi.

Videli sme rekurzívne a iteratívne prístupy k technike triedenia. Diskutovali sme tiež o triedení dátovej štruktúry Prepojený zoznam a ArrayList pomocou programu Mergesort.

V budúcich tutoriáloch budeme pokračovať v diskusii o ďalších technikách triedenia. Zostaňte naladení!

=> Navštívte tu sériu exkluzívnych výukových programov Java.

Odporúčané čítanie

^