streamalism.org

1. Inleiding

In deze tutorial zullen we kijken naar het Merge Sort-algoritme en de implementatie ervan in Java.

Samenvoegen is een van de meest efficiënte sorteertechnieken en is gebaseerd op het "verdeel en heers" -paradigma.

2. Het algoritme

Samenvoegsortering is een "verdeel en heers" -algoritme waarin we het probleem eerst in deelproblemen opdelen. Als de oplossingen voor de deelproblemen klaar zijn, combineren we ze samen om de uiteindelijke oplossing voor het probleem te krijgen.

Dit is een van de algoritmen die gemakkelijk kunnen worden geïmplementeerd met behulp van recursie, aangezien we de subproblemen aanpakken in plaats van het hoofdprobleem.

Het algoritme kan worden omschreven als het volgende proces in twee stappen:

• Verdelen: in deze stap verdelen we de invoerarray in 2 helften, waarbij het draaipunt het middelpunt van de array is. Deze stap wordt recursief uitgevoerd voor alle halve reeksen totdat er geen halve reeksen meer te verdelen zijn.
• Veroveren: in deze stap sorteren en voegen we de verdeelde arrays samen van onder naar boven en verkrijg de gesorteerde array.

Het volgende diagram toont het volledige samenvoegsorteerproces voor een voorbeeldmatrix {10, 6, 8, 5, 7, 3, 4}.

Als we het diagram van naderbij bekijken, kunnen we zien dat de array recursief in twee helften wordt verdeeld totdat de grootte 1 wordt. Zodra de grootte 1 wordt, treden de samenvoegprocessen in werking en beginnen ze arrays weer samen te voegen tijdens het sorteren:

3. Implementatie

Voor de uitvoering, we zullen een mergeSort functie die de invoerarray en zijn lengte overneemt als de parameters. Dit zal een recursieve functie zijn, dus we hebben de basis en de recursieve voorwaarden nodig.

De basisvoorwaarde controleert of de array-lengte 1 is en deze keert gewoon terug. Voor de rest van de gevallen wordt de recursieve aanroep uitgevoerd.

Voor het recursieve geval krijgen we de middelste index en maken we twee tijdelijke arrays l [] en r []. De mergeSort functie wordt dan recursief aangeroepen voor beide sub-arrays:

openbare statische leegte mergeSort (int [] a, int n) {if (n <2) {return; } int midden = n / 2; int [] l = nieuwe int [mid]; int [] r = nieuwe int [n - midden]; voor (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 - midden); samenvoegen (a, l, r, midden, n - midden); }

We noemen dan de samenvoegen functie die de invoer en zowel de sub-arrays als de begin- en eindindices van beide sub-arrays opneemt.

De samenvoegen functie vergelijkt de elementen van beide sub-arrays één voor één en plaatst het kleinere element in de invoerarray.

Wanneer we het einde van een van de sub-arrays bereiken, worden de rest van de elementen uit de andere array gekopieerd naar de invoerarray, waardoor we de laatste gesorteerde array krijgen:

openbare statische leegte samenvoegen (int [] a, int [] l, int [] r, int links, int rechts) {int i = 0, j = 0, k = 0; while (i <left && j <right) {if (l [i] <= r [j]) {a [k ++] = l [i ++]; } anders {a [k ++] = r [j ++]; }} while (i <left) {a [k ++] = l [i ++]; } while (j <rechts) {a [k ++] = r [j ++]; }} 

De unit-test voor het programma:

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

4. Complexiteit

Aangezien samenvoegsortering een recursief algoritme is, kan de tijdcomplexiteit worden uitgedrukt als de volgende recursieve relatie:

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

2T (n / 2) komt overeen met de tijd die nodig is om de subarrays en te sorteren Aan) tijd om de hele array samen te voegen.

Als het is opgelost, de tijd waarin complexiteit zal komen O (nLogn).

Dit geldt voor het slechtste, gemiddelde en beste geval, aangezien de array altijd in tweeën wordt gedeeld en vervolgens wordt samengevoegd.

De ruimtecomplexiteit van het algoritme is Aan) aangezien we tijdelijke arrays maken in elke recursieve aanroep.

5. Conclusie

In deze korte tutorial hebben we de werking van het samenvoegsorteeralgoritme gezien en hoe we het in Java kunnen implementeren.

De volledige werkende code is beschikbaar op GitHub.