Meniu

Merge Sort In Java - Program pentru implementarea MergeSort

  • Principal
  • Alte
  • Merge Sort In Java - Program pentru implementarea MergeSort

merge sort java program implement mergesort

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Acest tutorial explică ce este Merge Sort în Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Exemple de Iterative & Recursive MergeSort:

Tehnica de sortare Merge utilizează o strategie „Împarte și cucerește”. În această tehnică, setul de date care urmează a fi sortat este împărțit în unități mai mici pentru al sorta.

=> Citiți seria Easy Training Java.

Merge Sort In Java

Ce veți învăța:

Merge Sort In Java

De exemplu, dacă o matrice urmează să fie sortată utilizând mergesort, atunci matricea este împărțită în jurul elementului său de mijloc în două sub-tablouri. Aceste două sub-tablouri sunt împărțite în continuare în unități mai mici până când avem doar 1 element pe unitate.

Odată ce împărțirea este realizată, această tehnică îmbină aceste unități individuale prin compararea fiecărui element și sortarea lor la fuziune. Astfel, până când întreaga matrice este fuzionată înapoi, obținem o matrice sortată.

În acest tutorial, vom discuta toate detaliile acestei tehnici de sortare, în general, inclusiv algoritmul și pseudo-codurile sale, precum și implementarea tehnicii în Java.

Algoritm MergeSort în Java

Urmează algoritmul tehnicii.

# 1) Declarați o matrice myArray de lungime N

#Două) Verificați dacă N = 1, myArray este deja sortat

# 3) Dacă N este mai mare de 1,

  • set stânga = 0, dreapta = N-1
  • calculează mijloc = (stânga + dreapta) / 2
  • Apelați subrutina merge_sort (myArray, stânga, mijloc) => aceasta sortează prima jumătate a matricei
  • Apelați subrutina merge_sort (myArray, mijloc + 1, dreapta) => aceasta va sorta a doua jumătate a matricei
  • Apelați fuziunea subrutinei (myArray, stânga, mijloc, dreapta) pentru a fuziona matricele sortate în pașii de mai sus.

# 4) Ieșire

După cum se vede în pașii algoritmului, matricea este împărțită în două în mijloc. Apoi sortăm recursiv jumătatea stângă a matricei și apoi jumătatea dreaptă. Odată ce sortăm individual ambele jumătăți, acestea sunt îmbinate pentru a obține o matrice sortată.

Merge Sort Pseudo Code

Să vedem pseudo-codul pentru tehnica Mergesort. După cum sa discutat deja, deoarece aceasta este o tehnică de „împărțire și cucerire”, vom prezenta rutinele de împărțire a setului de date și apoi fuzionarea seturilor de date sortate.

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

În pseudo-codul de mai sus, avem două rutine, adică Mergesort și merge. Mergesort de rutină împarte matricea de intrare într-o matrice individuală care este suficient de ușor de sortat. Apoi apelează rutina de îmbinare.

Rutina de îmbinare îmbină sub-tablourile individuale și returnează o matrice sortată rezultată. După ce am văzut algoritmul și pseudo-codul pentru sortare Merge, să ilustrăm acum această tehnică folosind un exemplu.

MergeSort Ilustrație

Luați în considerare următoarea matrice care urmează să fie sortată folosind această tehnică.

Combinați ilustrația sortării

Acum, conform algoritmului de sortare Merge, vom împărți această matrice în elementul său mijlociu în două sub-tablouri. Apoi vom continua să împărțim sub-tablourile în tablouri mai mici până când vom obține un singur element în fiecare matrice.

Odată ce fiecare sub-matrice are un singur element în el, combinăm elementele. În timpul fuzionării, comparăm elementele și ne asigurăm că acestea sunt în ordine în matricea fuzionată. Așa că ne străduim să obținem o matrice fuzionată care este sortată.

Procesul este prezentat mai jos:

Merge procesul de sortare

După cum se arată în ilustrația de mai sus, vedem că matricea este împărțită în mod repetat și apoi fuzionată pentru a obține o matrice sortată. Având în vedere acest concept, să trecem la implementarea Mergesort în limbajul de programare Java.

Îmbinați implementarea sortării în Java

Putem implementa tehnica în Java folosind două abordări.

Sortare iterativă de îmbinare

Aceasta este o abordare de jos în sus. Sub-tablourile unui element sunt sortate și combinate pentru a forma matrici cu două elemente. Aceste matrici sunt apoi îmbinate pentru a forma matrici cu patru elemente și așa mai departe. În acest fel, matricea sortată este construită mergând în sus.

Exemplul Java de mai jos prezintă tehnica iterativă 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)); } }

Ieșire:

Matrice originală: (10, 23, -11, 54, 2, 9, -10, 45)
Matrice sortate: (-11, -10, 2, 9, 10, 23, 45, 54)

Sortare Merge Iterativă - Ieșire

Sortare recursivă de îmbinare

Aceasta este o abordare de sus în jos. În această abordare, matricea care trebuie sortată este împărțită în tablouri mai mici până când fiecare matrice conține doar un singur element. Apoi sortarea devine ușor de implementat.

Următorul cod Java implementează abordarea recursivă a tehnicii de sortare 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

Ieșire:

Matrice originală: (10, 23, -11, 54, 2, 9, -10, 45)
Matrice sortate: (- 11, -10, 2, 9, 10, 23, 45, 54)

MergeSort recursiv - ieșire

În secțiunea următoare, să trecem de la matrici și să folosim tehnica pentru a sorta structura de date a listelor legate și a listelor de matrice.

Sortează lista legată folosind Merge Sort în Java

Tehnica Mergesort este cea mai preferată pentru sortarea listelor legate. Alte tehnici de sortare au performanțe slabe atunci când vine vorba de lista legată din cauza accesului său în mare parte secvențial.

Următorul program sortează o listă legată folosind această tehnică.

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

Ieșire:

Lista originală legată:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nul
Listă legată sortată:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nul

descărcare de muzică mp3 aplicație gratuită de top

Ieșire - Sortează lista legată

Sortare ArrayList Folosind Merge Sort în Java

La fel ca matricele și listele legate, putem folosi această tehnică și pentru sortarea unei liste Array. Vom folosi rutine similare pentru a împărți recursiv ArrayList și apoi vom uni sublistele.

Codul Java de mai jos implementează tehnica de sortare Merge pentru 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(); } }

Ieșire:

Original ArrayList:
17 40 36 7 6 23 35 2 38
Listă matrice sortată:
2 6 7 17 23 35 36 38 40

Ieșire - Sortare ArrayList

întrebări frecvente

Q # 1) Sortarea Merge se poate face fără recursivitate?

Răspuns: Da. Putem efectua un sortare Merge nerecursivă numită „sortare Merge iterativă”. Aceasta este o abordare de jos în sus care începe prin fuzionarea sub-tablourilor cu un singur element într-o sub-matrice de două elemente.

Apoi, aceste sub-tablouri cu 2 elemente sunt îmbinate în sub-tablouri cu 4 elemente și așa mai departe folosind constructe iterative. Acest proces continuă până când avem o matrice sortată.

Q # 2) Sortarea Merge poate fi făcută la locul său?

Răspuns: Sortarea Merge nu este în general la locul său. Dar o putem face în loc utilizând o implementare inteligentă. De exemplu, prin stocarea valorii a două elemente într-o poziție. Acest lucru poate fi extras ulterior folosind modul și divizare.

Q # 3) Ce este un sortare Merge în 3 moduri?

Răspuns: Tehnica pe care am văzut-o mai sus este o sortare Merge în 2 direcții în care împărțim matricea pentru a fi sortată în două părți. Apoi sortăm și îmbinăm matricea.

Într-o sortare Merge în 3 direcții, în loc să împărțim matricea în 2 părți, o împărțim în 3 părți, apoi sortăm și în final o îmbinăm.

Q # 4) Care este complexitatea în timp a Mergesort?

Răspuns: Complexitatea de timp generală a sortării Merge în toate cazurile este O (nlogn).

Q # 5) Unde se folosește sortarea Merge?

Răspuns: Este folosit mai ales în sortarea listei legate în timp O (nlogn). Este, de asemenea, utilizat în scenarii distribuite în care datele noi apar în sistem înainte sau după sortare. Acesta este, de asemenea, utilizat în diferite scenarii de baze de date.

Concluzie

Sortarea Merge este o sortare stabilă și se realizează prin împărțirea mai întâi a setului de date în mod repetat în subseturi și apoi sortarea și combinarea acestor subseturi pentru a forma un set de date sortate. Setul de date este împărțit până când fiecare set de date este banal și ușor de sortat.

Am văzut abordările recursive și iterative ale tehnicii de sortare. Am discutat, de asemenea, sortarea structurii datelor Linked List și ArrayList folosind Mergesort.

Vom continua cu discuțiile despre mai multe tehnici de sortare în tutorialele noastre viitoare. Rămâneți aproape!

=> Vizitați aici pentru seria exclusivă de instruire Java.

Lectură recomandată

^