Menu

Flet sortering i Java - program til implementering af MergeSort

  • Vigtigste
  • Andet
  • Flet sortering i Java - program til implementering af MergeSort

merge sort java program implement mergesort

Prøv Vores Instrument Til At Fjerne Problemer

Denne vejledning forklarer, hvad der er Merge Sort i Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Eksempler på Iterativ & Rekursiv MergeSort:

Flettsorteringsteknik bruger en 'Divide-and-Conquer' -strategi. I denne teknik er datasættet, der skal sorteres, opdelt i mindre enheder for at sortere det.

=> Læs gennem Easy Java Training Series.

Flet sortering i Java

Hvad du lærer:

Flet sortering i Java

For eksempel, Hvis en matrix skal sorteres ved hjælp af fusionssortering, opdeles arrayet omkring det midterste element i to underarrays. Disse to underarrays er yderligere opdelt i mindre enheder, indtil vi kun har 1 element pr. Enhed.

Når delingen er færdig, fletter denne teknik disse individuelle enheder ved at sammenligne hvert element og sortere dem, når de flettes. På den måde, når hele arrayet flettes tilbage, får vi et sorteret array.

I denne vejledning diskuterer vi alle detaljerne i denne sorteringsteknik generelt inklusive dens algoritme og pseudokoder samt implementeringen af ​​teknikken i Java.

MergeSort-algoritme i Java

Følgende er algoritmen for teknikken.

# 1) Erklær en matrix myArray af længde N

#to) Kontroller, om N = 1, myArray er allerede sorteret

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

  • indstil venstre = 0, højre = N-1
  • beregne midten = (venstre + højre) / 2
  • Ring til subrutine merge_sort (myArray, left, middle) => dette sorterer første halvdel af arrayet
  • Ring til subrutine merge_sort (myArray, middle + 1, right) => dette sorterer anden halvdel af arrayet
  • Ring til subrutinefletning (myArray, venstre, midt, højre) for at flette arrays sorteret i ovenstående trin.

# 4) Afslut

Som det ses i algoritmetrinnene, er arrayet opdelt i to i midten. Derefter sorterer vi den venstre halvdel af arrayet og derefter den højre halvdel rekursivt. Når vi først har sorteret begge halvdele, flettes de sammen for at opnå et sorteret array.

Flet sorter Pseudo-kode

Lad os se pseudokoden til Mergesort-teknikken. Som allerede diskuteret, da dette er en 'divide-and-conquer' teknik, vil vi præsentere rutinerne for opdeling af datasættet og derefter sammenfletning af de sorterede datasæt.

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 ovenstående pseudokode har vi to rutiner, dvs. Mergesort og fusionere. Den rutinemæssige Mergesort opdeler input-arrayet i et individuelt array, der er let nok til at sortere. Derefter kalder det fusionsrutinen.

Fletningsrutinen fletter de individuelle underarrays og returnerer et resulterende sorteret array. Efter at have set algoritmen og pseudokoden for Flet sortering, lad os nu illustrere denne teknik ved hjælp af et eksempel.

MergeSort Illustration

Overvej følgende array, der skal sorteres ved hjælp af denne teknik.

Flet sorteringsillustration

I henhold til flettsorteringsalgoritmen deler vi dette array ved dets midterste element i to underarrays. Derefter vil vi fortsætte med at opdele underarrayerne i mindre arrays, indtil vi får et enkelt element i hvert array.

Når hver undergruppe kun har et element i sig, fletter vi elementerne sammen. Under fletning sammenligner vi elementerne og sikrer, at de er i orden i det flettede array. Så vi arbejder os op for at få et flettet array, der er sorteret.

Processen er vist nedenfor:

Flet sorteringsproces

Som vist i ovenstående illustration ser vi, at arrayet deles gentagne gange og derefter flettes for at få et sorteret array. Med dette koncept i tankerne, lad os gå videre til implementeringen af ​​Mergesort i Java-programmeringssprog.

Flet sorteringsimplementering i Java

Vi kan implementere teknikken i Java ved hjælp af to tilgange.

Iterativ flettsortering

Dette er en bottom-up-tilgang. Underarrangementer for hvert element sorteres og flettes for at danne to-element-arrays. Disse arrays flettes derefter for at danne fire-element arrays og så videre. På denne måde bygges det sorterede array ved at gå opad.

Nedenstående Java-eksempel viser den iterative Merge Sort-teknik.

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:

Original array: (10, 23, -11, 54, 2, 9, -10, 45)
Sorteret matrix: (-11, -10, 2, 9, 10, 23, 45, 54)

Iterativ flettsortering - output

Rekursiv flettsortering

Dette er en top-down-tilgang. I denne tilgang opdeles det array, der skal sorteres, i mindre arrays, indtil hvert array kun indeholder et element. Derefter bliver sorteringen let at implementere.

Den følgende Java-kode implementerer den rekursive tilgang til Merge-sorteringsteknikken.

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:

Original array: (10, 23, -11, 54, 2, 9, -10, 45)
Sorteret matrix: (- 11, -10, 2, 9, 10, 23, 45, 54)

Rekursivt MergeSort - output

I det næste afsnit, lad os skifte fra arrays og bruge teknikken til at sortere den sammenkædede liste og array listedatastrukturer.

Sorter linket liste ved hjælp af flettsortering i Java

Mergesort-teknik er den mest foretrukne til sortering af sammenkædede lister. Andre sorteringsteknikker fungerer dårligt, når det kommer til den sammenkædede liste på grund af dens mest sekventielle adgang.

Det følgende program sorterer en sammenkædet liste ved hjælp af denne teknik.

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:

Oprindelig sammenkædet liste:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Sorteret sammenkædet liste:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

type test i software engineering

Output - Sorter sammenkædet liste

Sorter ArrayList ved hjælp af Merge Sort i Java

Ligesom arrays og sammenkædede lister kan vi også bruge denne teknik til at sortere en ArrayList. Vi bruger lignende rutiner til at opdele ArrayList rekursivt og derefter flette underlisterne.

Nedenstående Java-kode implementerer Merge sort-teknikken til 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
Sorteret ArrayList:
2 6 7 17 23 35 36 38 40

Output - Sorter ArrayList

Ofte stillede spørgsmål

Q # 1) Kan flettsortering udføres uden rekursion?

Svar: Ja. Vi kan udføre en ikke-rekursiv flettesortering kaldet 'iterativ flettsortering'. Dette er en bottom-up-tilgang, der begynder med at flette underarrays med et enkelt element i et underarray med to elementer.

Derefter flettes disse 2-element-underarrays i 4-element-underarrays og så videre ved hjælp af iterative konstruktioner. Denne proces fortsætter, indtil vi har et sorteret array.

Q # 2) Kan flettsortering udføres på plads?

Svar: Flettsortering er generelt ikke på plads. Men vi kan gøre det på plads ved hjælp af en smart implementering. For eksempel, ved at gemme to elementværdier på en position. Dette kan ekstraheres bagefter ved hjælp af modul og division.

Q # 3) Hvad er en 3-vejs flettsortering?

Svar: Den teknik, vi har set ovenfor, er en 2-vejs flettsortering, hvor vi opdeler arrayet, der skal sorteres i to dele. Derefter sorterer vi og fletter arrayet.

I en 3-vejs flettsortering, i stedet for at opdele arrayet i 2 dele, deler vi det i 3 dele, sorterer derefter og slutter det sammen.

Q # 4) Hvad er tidskompleksiteten af ​​Mergesort?

Svar: Den samlede tidskompleksitet af flettsortering er i alle tilfælde O (nlogn).

Q # 5) Hvor bruges flettsorteringen?

Svar: Det bruges mest til at sortere den linkede liste i O (nlogn) tid. Det bruges også i distribuerede scenarier, hvor nye data kommer i systemet før eller efter sortering. Dette bruges også i forskellige databasescenarier.

Konklusion

Flettsortering er en stabil sortering og udføres ved først at opdele datasættet gentagne gange i delmængder og derefter sortere og flette disse delmængder for at danne et sorteret datasæt. Datasættet opdeles, indtil hvert datasæt er trivielt og let at sortere.

Vi har set de rekursive og iterative tilgange til sorteringsteknikken. Vi har også diskuteret sorteringen af ​​Linked List og ArrayList datastruktur ved hjælp af Mergesort.

Vi vil fortsætte med diskussionen om flere sorteringsteknikker i vores kommende tutorials. Bliv hængende!

=> Besøg her for den eksklusive Java-træningsundervisningsserie.

Anbefalet læsning

^