Merge Sort în Java

1. Introducere

În acest tutorial, vom arunca o privire asupra algoritmului Merge Sort și implementarea acestuia în Java .

Sortarea Merge este una dintre cele mai eficiente tehnici de sortare și se bazează pe paradigma „împarte și cucerește”.

2. Algoritmul

Sortarea Merge este un algoritm „împărțiți și cuceriți” în care mai întâi împărțim problema în subprobleme. Când soluțiile pentru subprobleme sunt gata, le combinăm împreună pentru a obține soluția finală a problemei.

Acesta este unul dintre algoritmii care pot fi implementați cu ușurință folosind recursivitatea, deoarece ne ocupăm mai degrabă de subprobleme decât de problema principală.

Algoritmul poate fi descris ca următorul proces în 2 pași:

  • Împărțiți: În acest pas, împărțim matricea de intrare în 2 jumătăți , pivotul fiind punctul de mijloc al matricei. Acest pas se realizează recursiv pentru toate jumătățile de matrice până când nu mai există jumătăți de matrice de divizat.
  • Conquer: În acest pas, sortăm și îmbinăm matricele împărțite de jos în sus și obținem matricea sortată.

Următoarea diagramă arată procesul complet de sortare a îmbinării pentru un exemplu de matrice {10, 6, 8, 5, 7, 3, 4}.

Dacă aruncăm o privire mai atentă asupra diagramei, putem vedea că matricea este împărțită recursiv în două jumătăți până când dimensiunea devine 1. Odată ce dimensiunea devine 1, procesele de îmbinare intră în acțiune și încep să îmbine matricile înapoi în timp ce sortăm:

3. Implementare

Pentru implementare, vom scrie o funcție mergeSort care ia în considerare matricea de intrare și lungimea acesteia ca parametri. Aceasta va fi o funcție recursivă, deci avem nevoie de bază și de condițiile recursive.

Condiția de bază verifică dacă lungimea matricei este 1 și va reveni. Pentru restul cazurilor, apelul recursiv va fi executat.

Pentru cazul recursiv, obținem indicele de mijloc și creăm două matrice temporare l [] și r [] . Funcția mergeSort este apoi apelată recursiv pentru ambele sub-tablouri:

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

Apelăm apoi la funcția de îmbinare care preia intrarea și atât sub-matricele, cât și indicii de început și de sfârșit ai ambelor sub-matrici .

Funcția de îmbinare compară elementele ambelor sub-tablouri unul câte unul și plasează elementul mai mic în matricea de intrare.

Când ajungem la sfârșitul uneia dintre sub-matrici, restul elementelor din cealaltă matrice sunt copiate în matricea de intrare, oferindu-ne astfel matricea finală sortată:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

Testul de unitate pentru program:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Complexitate

Deoarece sortarea de îmbinare este un algoritm recursiv, complexitatea timpului poate fi exprimată ca următoarea relație recursivă:

T(n) = 2T(n/2) + O(n)

2T (n / 2) corespunde timpului necesar pentru sortarea sub-tablourilor și O (n) timp pentru a fuziona întreaga matrice.

Când este rezolvată, complexitatea timpului va ajunge la O (nLogn).

Acest lucru este valabil pentru cel mai rău, mediu și cel mai bun caz, deoarece va împărți întotdeauna matricea în două și apoi se va uni.

Complexitatea spațială a algoritmului este O (n), deoarece creăm tablouri temporare în fiecare apel recursiv.

5. Concluzie

În acest tutorial rapid, am văzut funcționarea algoritmului de sortare a îmbinării și modul în care îl putem implementa în Java.

Întregul cod de lucru este disponibil pe GitHub.