Meni

Razvrsti spajanje v Javi - program za izvedbo razvrščanja

  • Glavni
  • Drugo
  • Razvrsti spajanje v Javi - program za izvedbo razvrščanja

merge sort java program implement mergesort

Preizkusite Naš Instrument Za Odpravo Težav

Ta vadnica pojasnjuje, kaj je združevanje v Java, algoritem MergeSort, psevdo koda, izvedba sortiranja spajanja, primeri iterativnega in rekurzivnega mergeSort:

Tehnika razvrščanja z združitvijo uporablja strategijo 'Divide-and-Conquer'. Pri tej tehniki je nabor podatkov, ki ga je treba razvrstiti, razdeljen na manjše enote za razvrščanje.

=> Preberite serijo Easy Java Training Series.

Združi razvrstitev v Javi

Kaj se boste naučili:

Združi razvrstitev v Javi

Na primer, če naj bo matrika razvrščena s pomočjo mergesort, je matrika razdeljena okoli svojega srednjega elementa na dve podniz. Ta dva podniza sta nadalje razdeljena na manjše enote, dokler nimamo samo 1 element na enoto.

Ko je delitev končana, ta tehnika združi te posamezne enote tako, da primerja vsak element in jih pri združevanju razvrsti. Na ta način, ko se celotno polje združi nazaj, dobimo razvrščeno polje.

V tej vadnici bomo razpravljali o vseh podrobnostih te tehnike razvrščanja na splošno, vključno z algoritmom in psevdo kodami, pa tudi o izvajanju tehnike v Javi.

MergeSort Algoritam v Javi

Sledi algoritem za tehniko.

# 1) Navedite polje myArray dolžine N

#two) Preverite, ali je N = 1, myArray je že razvrščen

# 3) Če je N večji od 1,

  • nastavite levo = 0, desno = N-1
  • izračuna sredino = (levo + desno) / 2
  • Pokliči podprogram merge_sort (myArray, levo, srednje) => to razvrsti prvo polovico polja
  • Pokliči podprogram merge_sort (myArray, srednji + 1, desno) => to bo razvrstilo drugo polovico polja
  • Pokličite združevanje podprograma (myArray, levo, sredino, desno), da združite nize, razvrščene v zgornjih korakih.

# 4) Izhod

Kot je razvidno iz korakov algoritma, je na sredini matrika razdeljena na dve. Nato rekurzivno razvrstimo levo polovico polja in nato desno polovico. Ko obe polovici posamično razvrstimo, se združita, da dobimo razvrščeno matriko.

Združi razvrščanje psevdo kode

Poglejmo psevdo-kodo za tehniko Mergesort. Kot je bilo že omenjeno, ker gre za tehniko 'deli in osvoji', bomo predstavili rutine za delitev nabora podatkov in nato združevanje razvrščenih naborov podatkov.

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

V zgornji psevdo-kodi imamo dve rutini, to je Mergesort in merge. Rutina Mergesort razdeli vhodno matriko na posamezno matriko, ki je dovolj enostavna za razvrščanje. Nato pokliče rutino spajanja.

Rutina spajanja združi posamezne podniz in vrne razvrščeno matriko. Potem ko smo videli algoritem in psevdo-kodo za razvrščanje Merge, ponazorimo to tehniko na primeru.

MergeSort ilustracija

Razmislite o naslednji matriki, ki bo razvrščena s to tehniko.

Slikovno razvrsti ilustracijo

Zdaj bomo v skladu z algoritmom za razvrščanje Merge razdelili to matriko v srednjem elementu na dve podniz. Nato bomo nadaljevali z razdeljevanjem pod nizov na manjše nize, dokler ne dobimo enega elementa v vsaki matriki.

Ko ima vsaka pod matrika samo en element, elemente združimo. Med združevanjem primerjamo elemente in zagotovimo, da so v združenem polju v redu. Torej se potrudimo, da dobimo razvrščeno matriko.

Postopek je prikazan spodaj:

Postopek razvrščanja med spajanjem

Kot je prikazano na zgornji sliki, vidimo, da je matrika večkrat razdeljena in nato združena, da dobimo razvrščeno matriko. S tem konceptom v mislih pojdimo na izvajanje Mergesorta v programskem jeziku Java.

Merge Sort Implementacija v Javi

Tehniko lahko v Java uporabimo z dvema pristopoma.

Iterativno združevanje

To je pristop od spodaj navzgor. Podmreže enega elementa so razvrščene in združene, da tvorijo dvoelementne nize. Nato se ti nizi združijo in tvorijo štirimestne nize itd. Tako je razvrščeno polje zgrajeno tako, da gre navzgor.

Spodnji primer Java prikazuje iterativno tehniko razvrščanja po združitvi.

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

Izhod:

Izvirno polje: (10, 23, -11, 54, 2, 9, -10, 45)
Razvrščeno polje: (-11, -10, 2, 9, 10, 23, 45, 54)

Iterativno združevanje - izhod

Rekurzivno razvrščanje

To je pristop od zgoraj navzdol. Pri tem pristopu se polje, ki ga je treba razvrstiti, razdeli na manjše nize, dokler vsako polje ne vsebuje samo enega elementa. Potem je razvrščanje enostavno izvedljivo.

Naslednja koda Java izvaja rekurzivni pristop tehnike razvrščanja 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

Izhod:

Izvirno polje: (10, 23, -11, 54, 2, 9, -10, 45)
Razvrščeno polje: (- 11, -10, 2, 9, 10, 23, 45, 54)

Rekurzivno mergeSort - izhod

V naslednjem razdelku preidimo z nizov in uporabimo tehniko za razvrščanje povezanih struktur podatkovnih struktur seznama in matrike.

Razvrščanje povezanega seznama s pomočjo spajanja Razvrsti v Javi

Tehnika spajanja je najbolj zaželena pri razvrščanju povezanih seznamov. Druge tehnike razvrščanja se pri povezanem seznamu zaradi večinoma zaporednega dostopa slabo obnesejo.

Naslednji program razvrsti povezani seznam s to tehniko.

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

Izhod:

Prvotni povezani seznam:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nično
Razvrščen povezan seznam:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nično

kako primerjati 2 datoteki v unixu

Izhod - Razvrsti povezan seznam

Razvrsti ArrayList z uporabo Merge Sort In Java

Tako kot seznami nizov in povezav lahko tudi to tehniko uporabimo za razvrščanje seznama ArrayList. Podobne rutine bomo uporabili za rekurzivno razdelitev seznama ArrayList in nato združevanje seznamov.

Spodnja Java koda izvaja tehniko razvrščanja Merge za 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(); } }

Izhod:

Original ArrayList:
17 40 36 7 6 23 35 2 38
Razvrščen seznam array:
2 6 7 17 23 35 36 38 40

Izhod - razvrsti seznam arrayList

Pogosto zastavljena vprašanja

V # 1) Ali lahko sortiranje spajanja izvedemo brez ponovitve?

Odgovor: Da. Izvedemo lahko nerekurzivno sortiranje, imenovano 'iterativno sortiranje spajanja'. To je pristop od spodaj navzgor, ki se začne z združevanjem podnizov z enim samim elementom v podpolje dveh elementov.

Nato se ti pod-nizi z 2 elementi združijo v pod-polja s 4 elementi in tako naprej z uporabo iterativnih konstruktov. Ta postopek se nadaljuje, dokler ne dobimo razvrščene matrike.

V # 2) Ali je mogoče razvrščanje merge opraviti na mestu?

Odgovor: Razvrščanje združitev na splošno ni na mestu. Lahko pa ga dosežemo na mestu z uporabo pametne izvedbe. Na primer, s shranjevanjem vrednosti dveh elementov na enem mestu. To lahko kasneje izvlečemo z uporabo modula in delitve.

3. vprašanje) Kaj je 3-način razvrščanja?

Odgovor: Tehnika, ki smo jo videli zgoraj, je dvosmerna sorta Merge, pri kateri smo matriko razdelili na dva dela. Nato matriko razvrstimo in združimo.

Pri 3-smernem razvrščanju Merge, namesto da razdelimo matriko na 2 dela, jo razdelimo na 3 dele, nato razvrstimo in na koncu združimo.

V # 4) Kakšna je časovna zapletenost Mergesorta?

Odgovor: Skupna časovna zapletenost razvrščanja Merge je v vseh primerih O (nlogn).

V # 5) Kje se uporablja sorta Merge?

Odgovor: Največkrat se uporablja pri razvrščanju povezanega seznama v času O (nlogn). Uporablja se tudi v porazdeljenih scenarijih, kjer novi podatki pridejo v sistem pred razvrščanjem ali naknadnim razvrščanjem. To se uporablja tudi v različnih scenarijih zbirke podatkov.

Zaključek

Razvrščanje po združitvi je stabilno razvrščanje in se izvede tako, da se nabor podatkov večkrat razdeli na podnabore in nato razvrsti in združi te podnabore, da se oblikuje razvrščeni nabor podatkov. Nabor podatkov je razdeljen, dokler ni vsak nabor podatkov nepomemben in ga je enostavno razvrstiti.

Videli smo rekurzivni in iterativni pristop k sortirni tehniki. Prav tako smo razpravljali o razvrščanju podatkovne strukture Povezani seznam in ArrayList z uporabo Mergesorta.

V naslednjih vajah bomo nadaljevali z razpravo o več tehnikah razvrščanja. Ostani na vezi!

=> Obiščite tukaj za ekskluzivno serijo vadnic Java.

Priporočeno branje

^