Meny

Merge Sort In Java - Program for å implementere MergeSort

  • Hoved
  • Annen
  • Merge Sort In Java - Program for å implementere MergeSort

merge sort java program implement mergesort

Prøv Instrumentet Vårt For Å Eliminere Problemer

Denne opplæringen forklarer hva som er Merge Sort i Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Eksempler på Iterative & Recursive MergeSort:

Merge sort-teknikk bruker en “Divide-and-Conquer” -strategi. I denne teknikken er datasettet som skal sorteres delt inn i mindre enheter for å sortere det.

=> Les gjennom Easy Java Training Series.

Slå sammen sortering i Java

Hva du vil lære:

Slå sammen sortering i Java

For eksempel, Hvis en matrise skal sorteres ved hjelp av sammenslåing, er matrisen delt rundt det midterste elementet i to underarrayer. Disse to undergruppene er videre delt inn i mindre enheter til vi bare har 1 element per enhet.

Når delingen er ferdig, smelter denne teknikken disse individuelle enhetene sammen ved å sammenligne hvert element og sortere dem når de slås sammen. På den måten når hele matrisen blir slått sammen, får vi en sortert matrise.

I denne opplæringen vil vi diskutere alle detaljene i denne sorteringsteknikken generelt, inkludert dens algoritme og pseudokoder, samt implementeringen av teknikken i Java.

MergeSort-algoritme i Java

Følgende er algoritmen for teknikken.

#1) Erklær en matrise myArray med lengde N

#to) Sjekk om N = 1, myArray er allerede sortert

# 3) Hvis N er større enn 1,

  • sett venstre = 0, høyre = N-1
  • beregne midten = (venstre + høyre) / 2
  • Kall subrutine merge_sort (myArray, left, middle) => dette sorterer første halvdel av arrayet
  • Ring subrutine merge_sort (myArray, midten + 1, høyre) => dette vil sortere andre halvdel av matrisen
  • Kall subrutinefusjon (myArray, venstre, midt, høyre) for å slå sammen matriser sortert i trinnene ovenfor.

# 4) Exit

Som det sees i algoritmetrinnene, er matrisen delt i to i midten. Så sorterer vi rekursivt den venstre halvdelen av matrisen og deretter den høyre halvdelen. Når vi hver gang har sortert begge halvdelene, blir de slått sammen for å oppnå en sortert matrise.

Slå sammen sortering av pseudokode

La oss se pseudokoden for Mergesort-teknikken. Som allerede diskutert siden dette er en 'divide-and-conquer' teknikk, vil vi presentere rutinene for å dele datasettet og deretter slå sammen de sorterte datasettene.

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

I ovennevnte pseudokode har vi to rutiner, dvs. Mergesort og flette. Den rutinemessige Mergesort deler inndata-arrayet i et individuelt array som er enkelt nok til å sortere. Da kaller det fusjonsrutinen.

Sammenslåingsrutinen slår sammen de enkelte underarrayene og returnerer en resulterende sortert matrise. Etter å ha sett algoritmen og pseudokoden for Merge sort, la oss nå illustrere denne teknikken ved hjelp av et eksempel.

MergeSort Illustrasjon

Tenk på følgende matrise som skal sorteres ved hjelp av denne teknikken.

Flett sorteringsillustrasjon

Nå, ifølge Merge sorteringsalgoritmen, vil vi dele denne matrisen ved midtelementet i to underarrayer. Deretter fortsetter vi å dele underarrayene i mindre matriser til vi får et enkelt element i hver matrise.

Når hver undergruppe bare har ett element i seg, slår vi sammen elementene. Mens vi slår sammen, sammenligner vi elementene og sørger for at de er i orden i den sammenslåtte matrisen. Så vi jobber oss opp for å få et sammenslått utvalg som er sortert.

Prosessen er vist nedenfor:

Flett sorteringsprosess

Som vist i illustrasjonen ovenfor ser vi at matrisen deles gjentatte ganger og deretter slås sammen for å få en sortert matrise. Med dette konseptet i tankene, la oss gå videre til implementeringen av Mergesort i Java-programmeringsspråk.

Merge Sort Implementation In Java

Vi kan implementere teknikken i Java ved hjelp av to tilnærminger.

Iterativ Merge Sort

Dette er en bottom-up-tilnærming. Underarrayene til hvert element sorteres og slås sammen for å danne to-element-arrays. Disse matriser blir deretter slått sammen for å danne fire-element matriser og så videre. På denne måten er den sorterte matrisen bygget ved å gå oppover.

Java-eksemplet nedenfor viser den iterative Merge Sort-teknikken.

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

Produksjon:

Original Array: (10, 23, -11, 54, 2, 9, -10, 45)
Sortert matrise: (-11, -10, 2, 9, 10, 23, 45, 54)

Iterativ flettesortering - utgang

Rekursiv flettesortering

Dette er en ovenfra og ned tilnærming. I denne tilnærmingen blir matrisen som skal sorteres, delt inn i mindre matriser til hver matrise inneholder bare ett element. Da blir sorteringen enkel å implementere.

Følgende Java-kode implementerer den rekursive tilnærmingen til Merge sort-teknikken.

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

Produksjon:

Original Array: (10, 23, -11, 54, 2, 9, -10, 45)
Sortert utvalg: (- 11, -10, 2, 9, 10, 23, 45, 54)

Rekursivt MergeSort - utgang

I neste avsnitt, la oss bytte fra matriser og bruke teknikken til å sortere datastrukturene for den sammenkoblede listen og matriselisten.

Sorter koblet liste ved hjelp av flette Sorter i Java

Mergesort-teknikk er den mest foretrukne for å sortere koblede lister. Andre sorteringsteknikker fungerer dårlig når det gjelder den koblede listen på grunn av den mest sekvensielle tilgangen.

Følgende program sorterer en koblet liste ved hjelp av denne teknikken.

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

Produksjon:

Opprinnelig koblet liste:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Sortert koblet liste:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

hvilken type test brukes for å verifisere at det nye systemet fungerer med faktiske data?

Output - Sorter koblet liste

Sorter ArrayList ved hjelp av Merge Sort In Java

I likhet med arrays og sammenkoblede lister, kan vi også bruke denne teknikken til å sortere en ArrayList. Vi vil bruke lignende rutiner for å dele ArrayList rekursivt og deretter slå sammen underlistene.

Java-koden nedenfor implementerer Merge sort-teknikken for 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(); } }

Produksjon:

Original ArrayList:
17 40 36 7 6 23 35 2 38
Sortert ArrayList:
2 6 7 17 23 35 36 38 40

Output - Sorter ArrayList

ofte stilte spørsmål

Q # 1) Kan flettesortering gjøres uten rekursjon?

Svar: Ja. Vi kan utføre en ikke-rekursiv Merge-sortering kalt ‘iterativ Merge sort’. Dette er en nedenfra og opp tilnærming som begynner med å slå sammen underordninger med et enkelt element i en undergruppe med to elementer.

Deretter blir disse 2-element-underarrayene slått sammen i 4-element-underarrays og så videre ved hjelp av iterative konstruksjoner. Denne prosessen fortsetter til vi har et sortert utvalg.

Q # 2) Kan Merge sort gjøres på plass?

Svar: Sammenslåing er vanligvis ikke på plass. Men vi kan gjøre det på plass ved å bruke en smart implementering. For eksempel, ved å lagre to elementverdier på en posisjon. Dette kan ekstraheres etterpå ved hjelp av modul og deling.

Q # 3) Hva er en 3-veis sammenslåingssortering?

Svar: Teknikken vi har sett ovenfor er en 2-veis Merge-sortering der vi deler arrayet som skal sorteres i to deler. Deretter sorterer og fletter vi matrisen.

I en 3-veis sammenslåingssortering, i stedet for å dele matrisen i to deler, deler vi den i 3 deler, og sorterer og til slutt fletter den.

Q # 4) Hva er tidskompleksiteten til Mergesort?

Svar: Den samlede tidskompleksiteten til Merge sort er i alle tilfeller O (nlogn).

Q # 5) Hvor brukes Merge-sorteringen?

Svar: Den brukes mest til å sortere den koblede listen i O (nlogn) tid. Den brukes også i distribuerte scenarier der nye data kommer i systemet før eller etter sortering. Dette brukes også i forskjellige databasescenarier.

Konklusjon

Flette sortering er en stabil sortering og utføres ved først å splitte datasettet gjentatte ganger i delsett og deretter sortere og slå sammen disse delsettene for å danne et sortert datasett. Datasettet er delt til hvert datasett er trivielt og enkelt å sortere.

Vi har sett de rekursive og iterative tilnærmingene til sorteringsteknikken. Vi har også diskutert sorteringen av Linked List og ArrayList datastruktur ved hjelp av Mergesort.

Vi vil fortsette med diskusjonen om flere sorteringsteknikker i våre kommende opplæringsprogrammer. Følg med!

=> Besøk her for den eksklusive opplæringsserien for Java Training.

Anbefalt lesing

^