Meni

Spajanje sortiranja u Javi - program za implementaciju MergeSort-a

  • Glavni
  • Ostalo
  • Spajanje sortiranja u Javi - program za implementaciju MergeSort-a

merge sort java program implement mergesort

Isprobajte Naš Instrument Za Uklanjanje Problema

Ovaj vodič objašnjava što je to Spajanje sortiranja u Javi, MergeSort algoritam, Pseudo kôd, Implementacija sortiranja stapanja, Primjeri iterativnog i rekurzivnog MergeSort:

Tehnika sortiranja spajanjem koristi strategiju 'Podijeli i osvoji'. U ovoj se tehnici skup podataka koji se sortira dijeli na manje jedinice da bi se sortirao.

=> Pročitajte seriju Easy Java Training.

Spajanje sortiranja u Javi

Što ćete naučiti:

Spajanje sortiranja u Javi

Na primjer, ako će se niz sortirati pomoću mergesort, tada je niz podijeljen oko svog srednjeg elementa u dva podniza. Ova dva podniza dalje su podijeljena u manje jedinice dok ne dobijemo samo 1 element po jedinici.

Nakon završetka podjele, ova tehnika spaja ove pojedinačne jedinice uspoređujući svaki element i sortirajući ih pri spajanju. Na taj način dok se čitav niz spoji natrag dobivamo sortirani niz.

U ovom ćemo uputstvu raspraviti sve detalje ove tehnike sortiranja općenito, uključujući algoritam i pseudo kodove, kao i provedbu tehnike u Javi.

MergeSort Algoritam u Javi

Slijedi algoritam za tehniku.

# 1) Proglasite niz myArray duljine N

#dva) Provjerite je li N = 1, myArray je već sortiran

# 3) Ako je N veći od 1,

  • postavljeno lijevo = 0, desno = N-1
  • izračunati sredinu = (lijevo + desno) / 2
  • Pozovite potprogram merge_sort (myArray, lijevo, sredina) => ovo sortira prvu polovicu niza
  • Pozovite potprogram merge_sort (myArray, middle + 1, right) => ovo će sortirati drugu polovicu niza
  • Pozovite spajanje potprograma (myArray, lijevo, srednje, desno) za spajanje nizova sortiranih u gornjim koracima.

# 4) Izlaz

Kao što se vidi u koracima algoritma, niz je u sredini podijeljen na dva dijela. Zatim rekurzivno sortiramo lijevu polovicu niza, a zatim desnu polovicu. Nakon što pojedinačno sortiramo obje polovice, one se spajaju zajedno da bi se dobio sortirani niz.

Spoji pseudo kod sortiranja

Pogledajmo pseudo-kôd za Mergesort tehniku. Kao što je već rečeno, budući da je ovo tehnika 'podijeli i osvoji', predstavit ćemo rutine za dijeljenje skupa podataka, a zatim spajanje razvrstanih skupova podataka.

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

U gornjem pseudo-kodu imamo dvije rutine, tj. Mergesort i merge. Rutina Mergesort razdvaja ulazni niz na pojedinačni niz koji je dovoljno jednostavan za sortiranje. Zatim poziva rutinu spajanja.

Rutina spajanja spaja pojedinačne podnizove i vraća rezultirajući sortirani niz. Nakon što smo vidjeli algoritam i pseudo-kôd za sortiranje spajanja, ilustrirajmo ovu tehniku ​​na primjeru.

MergeSort ilustracija

Razmotrite sljedeći niz koji će se sortirati pomoću ove tehnike.

Spajanje ilustracije

Sada ćemo prema algoritmu sortiranja spajanja podijeliti ovaj niz u njegovom srednjem elementu na dva podniza. Zatim ćemo nastaviti dijeliti podnizove na manje nizove dok ne dobijemo po jedan element u svakom nizu.

Jednom kada svaki pod-niz ima samo jedan element, mi spajamo elemente. Tijekom spajanja uspoređujemo elemente i osiguravamo da su u redu u spojenom nizu. Stoga se potrudimo kako bismo dobili spojeni niz koji je sortiran.

Postupak je prikazan u nastavku:

Postupak sortiranja spajanja

Kao što je prikazano na gornjoj ilustraciji, vidimo da se niz više puta dijeli i zatim spaja da bi se dobio sortirani niz. Imajući u vidu ovaj koncept, prijeđimo na implementaciju Mergesorta u programskom jeziku Java.

Implementacija sortiranja stapanja u Javi

Tehniku ​​u Java možemo implementirati pomoću dva pristupa.

Iterativno sortiranje spajanja

Ovo je pristup odozdo prema gore. Pod-nizovi po jednog elementa sortiraju se i spajaju tako da tvore nizove od dva elementa. Ti se nizovi zatim spajaju kako bi oblikovali nizove od četiri elementa i tako dalje. Na taj se način sortirani niz gradi prema gore.

Sljedeći primjer Java prikazuje iterativnu tehniku ​​sortiranja stapanja.

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

Izlaz:

Izvorni niz: (10, 23, -11, 54, 2, 9, -10, 45)
Sortirani niz: (-11, -10, 2, 9, 10, 23, 45, 54)

Iterativno sortiranje spajanja - izlaz

Rekurzivno sortiranje

Ovo je pristup od vrha prema dolje. U ovom se pristupu niz koji se razvrstava raščlanjuje na manje nizove dok svaki niz ne sadrži samo jedan element. Tada sortiranje postaje lako provesti.

Sljedeći Java kôd implementira rekurzivni pristup tehnike sortiranja 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

Izlaz:

Izvorni niz: (10, 23, -11, 54, 2, 9, -10, 45)
Sortirani niz: (- 11, -10, 2, 9, 10, 23, 45, 54)

Rekurzivni MergeSort - izlaz

U sljedećem odjeljku prebacimo se s polja i upotrijebimo tehniku ​​za sortiranje povezanih struktura podataka i popisa.

Poredaj povezani popis pomoću spajanja Poredaj u Javi

Mergesort tehnika je najpoželjnija za sortiranje povezanih popisa. Ostale tehnike sortiranja imaju loš učinak kada je u pitanju povezani popis zbog uglavnom sekvencijalnog pristupa.

Sljedeći program sortira povezani popis pomoću ove tehnike.

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

Izlaz:

Izvorni povezani popis:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Poredani povezani popis:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

Popis privatnih poslužitelja world of warcraft

Izlaz - sortiraj povezani popis

Poredaj ArrayList pomoću sortiranja stapanja u Javi

Poput nizova i povezanih popisa, i ovu tehniku ​​možemo koristiti za sortiranje popisa ArrayList. Upotrijebit ćemo slične rutine da rekurzivno podijelimo ArrayList, a zatim spojimo popise.

Sljedeći Java kôd implementira tehniku ​​sortiranja spajanja 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(); } }

Izlaz:

Izvorni popis nizova:
17 40 36 7 6 23 35 2 38
Poredani popis nizova:
2 6 7 17 23 35 36 38 40

Izlaz - sortiraj popis nizova

Često postavljana pitanja

P # 1) Može li se sortiranje spajanjem izvesti bez rekurzije?

Odgovor: Da. Možemo izvesti nerekurzivno sortiranje spajanja nazvano 'iterativno sortiranje spajanja'. Ovo je pristup odozdo prema gore koji započinje spajanjem pod-nizova s ​​jednim elementom u pod-niz od dva elementa.

Tada se ti pod-nizovi od 2 elementa spajaju u pod-nizove od 4 elementa i tako dalje koristeći iterativne konstrukcije. Taj se postupak nastavlja sve dok ne dobijemo razvrstani niz.

P # 2) Može li se sortiranje spajanjem obaviti na mjestu?

Odgovor: Sortiranje spajanja uglavnom nije na mjestu. Ali to možemo napraviti na mjestu pomoću neke pametne implementacije. Na primjer, pohranjivanjem vrijednosti dvaju elemenata na jednom mjestu. To se kasnije može izvući pomoću modula i dijeljenja.

3. pitanje) Što je trosmjerno sortiranje?

Odgovor: Tehnika koju smo vidjeli gore je dvosmjerna sortiranje spajanjem u kojoj podijelimo niz da bi se sortirao u dva dijela. Zatim sortiramo i spojimo niz.

U trosmjernom sortiranju Merge, umjesto da dijelimo niz na 2 dijela, mi ga dijelimo na 3 dijela, zatim sortiramo i konačno spajamo.

P # 4) Koja je vremenska složenost Mergesorta?

Odgovor: Ukupna vremenska složenost spajanja sortiranja u svim je slučajevima O (nlogn).

5. pitanje) Gdje se koristi sortiranje spajanja?

Odgovor: Uglavnom se koristi za sortiranje povezanog popisa u O (nlogn) vremenu. Također se koristi u distribuiranim scenarijima u kojima novi podaci dolaze u sustav prije ili nakon sortiranja. To se također koristi u različitim scenarijima baze podataka.

Zaključak

Spajanje sortiranja je stabilno sortiranje i izvodi se tako da se skup podataka prvo više puta podijeli u podskupove, a zatim sortira i spoji te podskupove kako bi se oblikovao sortirani skup podataka. Skup podataka dijeli se dok svaki skup podataka nije trivijalan i jednostavan za sortiranje.

Vidjeli smo rekurzivni i iterativni pristup tehnici sortiranja. Također smo razgovarali o sortiranju strukture podataka Povezanog popisa i ArrayList pomoću Mergesorta.

Nastavit ćemo s raspravom o više tehnika sortiranja u našim nadolazećim vodičima. Pratite nas!

=> Posjetite ovdje za ekskluzivnu seriju udžbenika za Java.

Preporučena literatura

^