Slå samman sortering i Java

1. Introduktion

I den här handledningen tar vi en titt på Merge Sort-algoritmen och dess implementering i Java .

Sammanfogningssortering är en av de mest effektiva sorteringsteknikerna och den bygger på paradigmet ”dela och erövra”.

2. Algoritmen

Merge sort är en "dela och erövra" -algoritm där vi först delar upp problemet i delproblem. När lösningarna för delproblemen är färdiga kombinerar vi dem för att få den slutliga lösningen på problemet.

Detta är en av algoritmerna som enkelt kan implementeras med rekursion eftersom vi hanterar delproblemen snarare än huvudproblemet.

Algoritmen kan beskrivas som följande tvåstegsprocess:

  • Dela: I det här steget delar vi inmatningsmatrisen i två halvor , varvid ledpunkten är mittpunkten för matrisen. Detta steg utförs rekursivt för alla halvmatriserna tills det inte finns fler halvmatriser att dela.
  • Conquer: I det här steget sorterar vi och sammanfogar de delade matriserna från botten till toppen och får den sorterade matrisen.

Följande diagram visar den fullständiga sammanslagningssorteringsprocessen för en exempelmatris {10, 6, 8, 5, 7, 3, 4}.

Om vi ​​tar en närmare titt på diagrammet kan vi se att matrisen är rekursivt uppdelad i två halvor tills storleken blir 1. När storleken blir 1, går sammanfogningsprocesserna till handling och börjar sammanfoga arrayer under sortering:

3. Implementering

För implementeringen skriver vi en mergeSort- funktion som tar in inmatningsmatrisen och dess längd som parametrar. Detta kommer att vara en rekursiv funktion så vi behöver basen och de rekursiva förhållandena.

Basvillkoret kontrollerar om matrislängden är 1 och att den bara kommer tillbaka. I övriga fall kommer det rekursiva samtalet att genomföras.

För det rekursiva fallet får vi mittindex och skapar två tillfälliga matriser l [] och r [] . Den mergesort funktionen kallas då rekursivt både under arrayer:

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

Vi kallar sedan sammanslagningsfunktionen som tar in ingången och både undergrupperna och start- och slutindexen för båda undergrupperna .

Den merge funktion jämför elementen i båda underarrangemang en efter en och placerar det mindre elementet i inputuppställningen.

När vi når slutet av en av undergrupperna kopieras resten av elementen från den andra matrisen till inmatningsmatrisen, vilket ger oss den slutliga sorterade matrisen:

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++]; } } 

Enhetstestet för programmet:

@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. Komplexitet

Eftersom sammanslagning är en rekursiv algoritm kan tidskomplexiteten uttryckas som följande rekursiva relation:

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

2T (n / 2) motsvarar den tid som krävs för att sortera undermatriserna och O (n) tid för att slå samman hela matrisen.

När det är löst kommer tidskomplexiteten till O (nLogn).

Detta gäller sämsta, genomsnittliga och bästa fallet eftersom det alltid kommer att dela upp arrayen i två och sedan slå ihop.

Algoritmens rymdkomplexitet är O (n) eftersom vi skapar tillfälliga matriser i varje rekursivt samtal.

5. Sammanfattning

I denna snabba handledning såg vi hur sorteringsalgoritmen fungerar och hur vi kan implementera den i Java.

Hela arbetskoden finns tillgänglig på GitHub.