streamalism.org

1. Introduksjon

I denne veiledningen tar vi en titt på Merge Sort-algoritmen og implementeringen av den i Java.

Flette sortering er en av de mest effektive sorteringsteknikkene, og den er basert på paradigmet “del og erobre”.

2. Algoritmen

Merge sort er en "del og erobre" -algoritme der vi først deler problemet i delproblemer. Når løsningene for delproblemene er klare, kombinerer vi dem sammen for å få den endelige løsningen på problemet.

Dette er en av algoritmene som enkelt kan implementeres ved hjelp av rekursjon når vi håndterer delproblemene i stedet for hovedproblemet.

Algoritmen kan beskrives som følgende 2-trinnsprosess:

• Del: I dette trinnet deler vi inngangsoppsettet i to halvdeler, hvor svingpunktet er midtpunktet i matrisen. Dette trinnet utføres rekursivt for alle halvpartene til det ikke er flere halvdeler å dele.
• Conquer: I dette trinnet sorterer og fletter vi de delte matriser fra bunn til topp og få den sorterte matrisen.

Diagrammet nedenfor viser den fullstendige sammenslåingssorteringsprosessen for et eksempel array {10, 6, 8, 5, 7, 3, 4}.

Hvis vi ser nærmere på diagrammet, kan vi se at matrisen er rekursivt delt inn i to halvdeler til størrelsen blir 1. Når størrelsen blir 1, kommer sammenslåingsprosessene til handling og begynner å slå sammen arrays tilbake mens du sorterer:

3. Gjennomføring

For implementeringen, vi skriver en mergeSort funksjon som tar inn inngangsmatrisen og dens lengde som parameterne. Dette vil være en rekursiv funksjon, så vi trenger basen og de rekursive forholdene.

Grunntilstanden sjekker om matriselengden er 1, og den kommer bare tilbake. For resten av sakene vil det rekursive anropet bli utført.

For det rekursive tilfellet får vi midtindeksen og lager to midlertidige matriser l [] og r []. De mergeSort funksjon kalles deretter rekursivt for begge underarrayene:

offentlig statisk tomrom mergeSort (int [] a, int n) {if (n <2) {return; } int midt = n / 2; int [] l = ny int [mid]; int [] r = ny int [n - midt]; 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); fusjonere (a, l, r, mid, n - mid); }

Vi kaller deretter slå sammen funksjon som tar inn inngangen og både underarrayene og start- og sluttindeksene til begge underarrayene.

De slå sammen funksjon sammenligner elementene i begge underarrayene en etter en og plasserer det mindre elementet i inngangsruten.

Når vi når slutten av en av underarrayene, blir resten av elementene fra den andre matrisen kopiert til inngangsmatrisen og gir oss den endelige sorterte matrisen:

offentlig statisk tomrumsfletting (int [] a, int [] l, int [] r, int venstre, int høyre) {int i = 0, j = 0, k = 0; mens (i <venstre && j <høyre) {if (l [i] <= r [j]) {a [k ++] = l [i ++]; } annet {a [k ++] = r [j ++]; }} mens (i <venstre) {a [k ++] = l [i ++]; } mens (j <høyre) {a [k ++] = r [j ++]; }} 

Enhetstesten for programmet:

@Test offentlig ugyldig positiveTest () {int [] faktisk = {5, 1, 6, 2, 3, 4}; int [] forventet = {1, 2, 3, 4, 5, 6}; MergeSort.mergeSort (faktisk, faktisk.lengde); assertArrayEquals (forventet, faktisk); }

4. Kompleksitet

Ettersom flettesortering er en rekursiv algoritme, kan tidskompleksiteten uttrykkes som følgende rekursive forhold:

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

2T (n / 2) tilsvarer tiden det tar å sortere underarrayene og På) tid til å slå sammen hele matrisen.

Når det er løst, tidskompleksiteten vil komme til O (nLogn).

Dette gjelder i verste, gjennomsnittlige og beste tilfelle, siden det alltid vil dele matrisen i to og deretter slå seg sammen.

Romkompleksiteten til algoritmen er På) når vi lager midlertidige matriser i hvert rekursivt anrop.

5. Konklusjon

I denne raske veiledningen så vi hvordan algoritmen for sammenslåingssortering fungerer og hvordan vi kan implementere den i Java.

Hele arbeidskoden er tilgjengelig på GitHub.