Meny

Merge Sort In Java - Program för att implementera MergeSort

  • Huvud
  • Övrig
  • Merge Sort In Java - Program för att implementera MergeSort

merge sort java program implement mergesort

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning förklarar vad som är Merge Sort i Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Exempel på Iterative & Recursive MergeSort:

Merge sort-teknik använder en ”Divide-and-Conquer” -strategi. I denna teknik delas datauppsättningen som ska sorteras i mindre enheter för att sortera den.

=> Läs igenom Easy Java Training Series.

Slå ihop sortering i Java

Vad du kommer att lära dig:

Slå ihop sortering i Java

Till exempel, om en matris ska sorteras med hjälp av sammanslagning, delas matrisen runt dess mittelement i två underarrayer. Dessa två undergrupper är vidare uppdelade i mindre enheter tills vi bara har 1 element per enhet.

När uppdelningen är klar, kombinerar denna teknik dessa enskilda enheter genom att jämföra varje element och sortera dem när de slås ihop. På det här sättet när hela arrayen slås samman får vi en sorterad array.

I denna handledning kommer vi att diskutera alla detaljer i denna sorteringsteknik i allmänhet inklusive dess algoritm- och pseudokoder samt implementeringen av tekniken i Java.

MergeSort-algoritm i Java

Nedan följer algoritmen för tekniken.

# 1) Förklara en array myArray av längd N

#två) Kontrollera om N = 1, myArray är redan sorterat

# 3) Om N är större än 1,

  • ställ in vänster = 0, höger = N-1
  • beräkna mitten = (vänster + höger) / 2
  • Ring subrutin merge_sort (myArray, left, middle) => det här sorterar första hälften av arrayen
  • Ring subrutin merge_sort (myArray, mitten + 1, höger) => så sorteras den andra halvan av arrayen
  • Ring subrutinfusion (myArray, vänster, mitt, höger) för att slå samman matriser sorterade i ovanstående steg.

# 4) Utgång

Som framgår av algoritmstegen är arrayen uppdelad i två i mitten. Sedan sorterar vi rekursivt den vänstra halvan av matrisen och sedan den högra halvan. När vi väl har sorterat båda halvorna individuellt slås de samman för att få en sorterad matris.

Slå ihop sortering av pseudokod

Låt oss se pseudokoden för Mergesort-tekniken. Som redan diskuterats eftersom detta är en 'dela och erövra' -teknik kommer vi att presentera rutinerna för att dela datamängden och sedan slå samman de sorterade datamängderna.

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 ovanstående pseudokod har vi två rutiner, dvs Mergesort och merge. Den rutinmässiga Mergesort delar inmatningsmatrisen i en individuell matris som är lätt att sortera. Då kallar det sammanslagningsrutinen.

Sammanfogningsrutinen slår samman de enskilda undergrupperna och returnerar en resulterande sorterad matris. Efter att ha sett algoritmen och pseudokoden för Merge sort, illustrerar vi nu den här tekniken med ett exempel.

MergeSort Illustration

Tänk på följande array som ska sorteras med den här tekniken.

Sammanfoga sorteringsillustration

Nu enligt Merge sorteringsalgoritmen kommer vi att dela upp den här matrisen vid dess mittelement i två underarrayer. Sedan kommer vi att fortsätta dela delmatriserna i mindre matriser tills vi får ett enda element i varje matris.

När varje undergrupp bara har ett element i sig slår vi samman elementen. Under sammanslagningen jämför vi elementen och ser till att de är i ordning i den sammanslagna matrisen. Så vi jobbar oss upp för att få en sammanslagen matris som sorteras.

Processen visas nedan:

Sammanfoga sorteringsprocessen

Som visas i ovanstående illustration ser vi att arrayen delas upprepade gånger och sedan slås samman för att få en sorterad array. Med detta koncept i åtanke, låt oss gå vidare till implementeringen av Mergesort i Java-programmeringsspråk.

Sammanfoga sorteringsimplementering i Java

Vi kan implementera tekniken i Java med två metoder.

Iterativ sammanslagningssortering

Detta är en bottom-up-strategi. Undergrupperna för ett element vardera sorteras och slås samman för att bilda tvåelementmatriser. Dessa matriser slås sedan samman för att bilda fyrelementmatriser och så vidare. På så sätt byggs den sorterade matrisen genom att gå uppåt.

Nedanstående Java-exempel visar den iterativa Merge Sort-tekniken.

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

Produktion:

Originalmatris: (10, 23, -11, 54, 2, 9, -10, 45)
Sorterad matris: (-11, -10, 2, 9, 10, 23, 45, 54)

Iterativ sammanslagningssortering - Output

Rekursiv sammanslagningssortering

Detta är en uppifrån och ner strategi. I detta tillvägagångssätt delas den matris som ska sorteras upp i mindre matriser tills varje matris bara innehåller ett element. Då blir sorteringen lätt att genomföra.

Följande Java-kod implementerar den rekursiva metoden för Merge sort-tekniken.

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

Produktion:

Originalmatris: (10, 23, -11, 54, 2, 9, -10, 45)
Sorterad matris: (- 11, -10, 2, 9, 10, 23, 45, 54)

Rekursivt MergeSort - Output

I nästa avsnitt, låt oss byta från matriser och använda tekniken för att sortera den länkade listan och matrislistan datastrukturer.

Sortera länkad lista med Merge Sortera i Java

Mergesort-teknik är den mest föredragna för att sortera länkade listor. Andra sorteringstekniker fungerar dåligt när det gäller den länkade listan på grund av dess mestadels sekventiella åtkomst.

Följande program sorterar en länkad lista med den här tekniken.

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

Produktion:

Originallänkad lista:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Sorterad länkad lista:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

oops begrepp i c # med exempel för erfarna

Output - Sortera länkad lista

Sortera ArrayList med Merge Sort i Java

Liksom Arrays och länkade listor kan vi också använda denna teknik för att sortera en ArrayList. Vi kommer att använda liknande rutiner för att dela ArrayList rekursivt och sedan slå samman sublistorna.

Nedanstående Java-kod implementerar Merge sort-tekniken för 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(); } }

Produktion:

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

Output - Sort ArrayList

Vanliga frågor

F # 1) Kan slåssortering göras utan rekursion?

Svar: Ja. Vi kan utföra en icke-rekursiv sammanslagningssort som kallas ”iterativ sammanslagningssortering”. Detta är en nedifrån och upp-metod som börjar med att slå samman underarrayer med ett enda element i en undergrupp med två element.

Därefter slås dessa 2-element underarrayer samman i 4-element underarrayer och så vidare med iterativa konstruktioner. Denna process fortsätter tills vi har en sorterad matris.

F # 2) Kan Merge sorteras på plats?

Svar: Sammanfogningssortering är vanligtvis inte på plats. Men vi kan göra det på plats genom att använda någon smart implementering. Till exempel, genom att lagra två elementvärden i en position. Detta kan extraheras efteråt med hjälp av modul och division.

F # 3) Vad är en trevägssorteringssortering?

Svar: Tekniken vi har sett ovan är en 2-vägs sammanslagningssortering där vi delar upp matrisen som ska sorteras i två delar. Sedan sorterar vi och slår ihop matrisen.

I en 3-vägs sammanslagningssortering, istället för att dela upp matrisen i två delar, delar vi den i tre delar, sorterar sedan och slutligen slår ihop den.

F # 4) Vad är tidskomplexiteten hos Mergesort?

Svar: Den totala tidskomplexiteten för Merge sort är i alla fall O (nlogn).

F # 5) Var används sorteringssammanslagningen?

Svar: Den används mest för att sortera den länkade listan under O (nlogn) -tid. Det används också i distribuerade scenarier där nya data kommer i systemet före eller efter sortering. Detta används också i olika databasscenarier.

Slutsats

Sammanfoga sortering är en stabil sortering och utförs genom att dela upp datamängden upprepade gånger i delmängder och sedan sortera och slå samman dessa delmängder för att bilda en sorterad datamängd. Datamängden delas upp tills varje datamängd är trivial och lätt att sortera.

Vi har sett de rekursiva och iterativa metoderna för sorteringstekniken. Vi har också diskuterat sorteringen av länkad lista och ArrayList datastruktur med hjälp av Mergesort.

Vi kommer att fortsätta med diskussionen om fler sorteringstekniker i våra kommande handledning. Håll dig uppdaterad!

=> Besök här för den exklusiva Java-utbildningsserien.

Rekommenderad läsning

^