Slå sammen i Java forklart

En liste eller matrise hvis indeksering (telling) begynner fra null kan halveres. Spørsmålet er, når det totale antallet elementer i listen er rart, hva er venstre halvdel og hva som er høyre halvdel. Når det totale antallet elementer er jevn, er det ikke noe problem. Hvis lengden på listen er 8, si, har venstre halvdel de 4 første elementene, og høyre halvdel har de neste 4 elementene. Hvis lengden på listen er 5, for eksempel, som er merkelig, har venstre halvdel de tre første elementene, og høyre halvdel har de neste 2 elementene.

Hvis lengden på listen er 8, anses indeksen for Mid (midt) element å være 3, som det er, det fjerde elementet - indekstelling begynner fra 0. Så når lengden på listen er jevn, er indeksen for midtelementet lengde / 2 - 1.

Hvis lengden på listen er 5, anses indeksen for midtelementet å være 2, som er det tredje elementet. Så når lengden på listen er merkelig, er indeksen for midtelementet lengde / 2 - 1/2.

Det er ikke vanskelig å få midt-indeksen til en liste med Java! - Bare bruk heltall aritmetikk. Uttrykket for Mid -indeksen er:

høyestindex / 2

Så hvis lengden er 8, er den høyeste indeksen, som er 7, delt med 2 for å gi 3 og en 1/2. Heltall aritmetikk kaster halvparten, og etterlater deg 3, som er lengde / 2 - 1.

Hvis lengden er 5, er den høyeste indeksen, som er 4, delt med 2 for å gi 2, som er, lengde / 2 - 1/2.

Merge -sort er en sorteringsalgoritme. I denne opplæringen vil sorteringen resultere i en endelig liste, fra minst til høyeste verdi. Merge sort bruker skillet og erobrer paradigme. Resten av denne opplæringen forklarer at det gjelder Java.

Artikkelinnhold

• Del og erobre for Merge Sort
• Den viktigste rekursjonsmetoden
• Conquer () -metoden
• Midlertidig matrise for Conquer () -metoden
• Konklusjon

Del og erobre for Merge Sort

Del betyr å dele den usorterte listen i to halvdeler, som forklart ovenfor. Del deretter hver av halvdelene i to halvdeler til. Fortsett å dele de resulterende halvdelene til det er N -lister over ett element hver, der N er lengden på den opprinnelige listen.

Conquerer betyr å begynne å sammenkoble påfølgende lister i en liste mens du sorterer den resulterende listen. Parringen fortsetter til en endelig sortert liste over lengder som er lik den opprinnelige lengden, oppnås.

Tenk på den usorterte listen over alfabetiske bokstaver:

M k q c e t g

Lengden på denne listen er 7. Følgende diagram illustrerer hvordan sammenslåing av denne listen gjøres i teorien:

Fra diagrammet tar divisjonen til enkeltverdier 3 trinn. Conquer, som er sammenslåing og sortering, tar ytterligere 3 trinn for å ha den sorterte sluttlisten.

Skulle en programmerer skrive 6 kodesegmenter for å oppnå dette? - Nei. Programmereren må ha en rekursjonsordning ved hjelp av en midlertidig liste.

Legg ikke merke til at G ser ganske merkelig ut i sin posisjonering for deling av første høyre halvdel. Dette er fordi lengden på listen er et oddetall, 7. Hvis lengden var et jevnt tall, si 6, ville Q virket som merkelig på en lignende måte for inndelingen av første venstre halvdel.

Resten av denne artikkelen forklarer “Fett sort i Java”, ved å bruke den usorterte listen:

M k q c e t g

Den viktigste rekursjonsmetoden

Det er tre metoder i dette programmet. Metodene er, Divide () -metoden, Conquer () -metoden og Main () -metoden. Divide () -metoden er hovedmetoden. Det kaller seg gjentatte ganger for venstre og høyre halvdel og kaller Conquerer () -metoden på slutten av kroppen. Koden for hovedmetoden er:

void Divide (char arr [], int teg, int end)
int midt;
hvis (tigger < end)
Mid = (Beg + End)/2;
del (arr, tig, midt);
Del (arr, midt+1, ende);
Conquer (arr, Beg, Mid, End);

I starten tar det matrisen som er gitt, Beginning (BEG) Array Index, som er 0, og slutt -arrayindeksen, som er 6. Metoden vil ikke utføres hvis den ikke har minst to elementer. Sjekken gjøres av IF-kondisjonen, “IF (tigger < end)”. The first divide() recall calls the left half of the list, and the second divide() recall calls the right to half of the list.

Så for den første utførelsen eller passet, av Divide () -metoden, er IF-kondisjonen fornøyd (mer enn ett element). Mid -indeksen er 3 = (0 + 6) / 2 (heltall aritmetikk). De tre metodene og deres ordre med argumentene deres blir:

del (arr, 0, 3);
del (arr, 4, 6);
Conquer (arr, 0, 3, 6);

Det er tre samtaler her. Den første av disse samtalene, kaller Divide () -metoden igjen for venstre halvdel av listen. De to andre metodene er notert og reservert i deres orden, som skal utføres senere. Det andre Divide () -samtalen vil kalle Divide () -metoden for høyre halvdel av listen. Conquer -metoden ville utføre de to første halvdelene sammen.

Før den andre passet for Divide () -metoden, bør listen betraktes som deles i to som følger:

M k q c e t g

I den andre passet til Divide () -metoden blir venstre halvdel av listen ivaretatt til. Oppfordringen til det andre passet er:

del (arr, 0, 3);

Denne gangen er midtindeksen, 1 = (0 + 3) / 2 (heltall aritmetikk). Metoden ringer, deres orden og argumenter blir,

del (arr, 0, 1);
del (arr, 2, 3);
Conquer (arr, 0, 1, 3);

Merk at den nye sluttindeksen er 3, som er slutten på første venstre halvdel. Den første av disse samtalene, kaller Divide () -metoden igjen for venstre halvdel av den første venstre halvdelen av listen. De to andre metodene blir notert og reservert i deres orden, som skal utføres senere, med sine nye argumenter. Det andre Divide () -samtalen vil kalle Divide () -metoden for høyre halvdel av den første venstre halvdelen av listen. Conquer () -metoden ville utføre de to nye halvdelene.

Før den tredje passet for Divide () -metoden, bør listen betraktes som delt som følger:

M k q c e t g

Den tredje passering av skillemetoden er samtalen:

del (arr, 0, 1);

I denne tredje passering av Divide () -metoden blir den venstre halvdelen av den nye underlisten det spørsmålet ivaretatt ivaretatt. Denne gangen er midtindeksen, 0 = (0 + 1) / 2 (heltall aritmetikk). Metoden ringer, deres orden og argumenter blir,

del (arr, 0, 0);
del (arr, 1, 1);
Conquer (arr, 0, 0, 1);

Merk at den nye sluttindeksen er 1, som er slutten på den nye venstre halvdelen. Den første av disse samtalene er,

del (arr, 0, 0);

Det mislykkes på grunn av hvis du < end)” - beg, and end are the same, meaning there is only one element. The second divide() method,

del (arr, 1, 1);

Mislykkes også av en lignende grunn. På dette tidspunktet bør listen betraktes som delt som,

M k q c e t g

Den tredje samtalen er:

Conquer (arr, 0, 0, 1);

Conquer Call for de to underlistene er M og K, hver bestående av ett element. Conquer () -metoden smelter sammen og sorterer to underlister. Den resulterende underlisten ville være k m. Hele listen ville bli:

K m q c e t g

Husk at det er metoder, som ble bemerket og reservert. De vil bli kalt i omvendt rekkefølge, nå med,

del (arr, 2, 3);

Dette er fjerde passering av Divide () -metoden. Det er for å håndtere underlisten, Q C, hvis begynnelsesindeks er 2 og sluttindeksen er 3. Mid -indeksen er nå 2 = (2 + 3) / 2 (heltall aritmetikk). Metoden ringer, deres orden og argumenter blir,

del (arr, 2, 2);
del (arr, 3, 3);
Conquer (arr, 2, 2, 3);

Den femte passering av Divide () -metoden er samtalen,

del (arr, 2, 2);

Merk at begynnelses- og sluttindeksen er den samme, noe som betyr at det bare er ett element. Denne samtalen mislykkes, på grunn av IF-kondisjonen, “IF (tigger < end)”. The second divide() call,

del (arr, 3, 3);

Mislykkes også av samme grunn. På dette tidspunktet bør listen betraktes som delt som,

K m q c e t g

Den tredje samtalen i metodepasset er:

Conquer (arr, 2, 2, 3);

Conquerer oppfordring til de to underlistene er Q og C, hver bestående av ett element. Conquer () -metoden smelter sammen og sorterer to underlister. Den resulterende underlisten ville være C Q. Hele listen ville bli:

K m c q e t g

Husk at det fremdeles er metoder, som ble bemerket og reservert. De vil fortsette å bli kalt i omvendt rekkefølge; nå med,

del (arr, 4, 6);

Dette er den sjette passet til Divide () -metoden. Det er for å håndtere underlisten, E T G, hvis begynnelsesindeks er 4 og sluttindeksen er 6. Mid -indeksen er nå 5 = (4 + 6) / 2 (heltall aritmetikk). Metoden ringer, deres orden og argumenter blir,

del (arr, 4, 5);
del (arr, 5, 6);
Conquer (arr, 4, 5, 6);

Den syvende passering av Divide () -metoden er samtalen,

del (arr, 4, 5);

De to andre samtalene er notert og reservert. Merk at den nye sluttindeksen er 5, som er slutten på den nye venstre halvdelen. Mid -indeksen er nå 4 = (4 + 5) / 2 (heltall aritmetikk). Metoden ringer, deres orden og argumenter blir,

del (arr, 4, 4);
del (arr, 5, 5);
Conquer (arr, 4, 4, 5);

Åttende passet er:

del (arr, 4, 4);

Merk at begynnelses- og sluttindeksen er den samme, noe som betyr at det bare er ett element. Denne samtalen mislykkes, på grunn av IF-kondisjonen, “IF (tigger < end)”. The second divide() method call is,

del (arr, 5, 5);

Som også mislykkes av samme grunn. På dette tidspunktet bør listen betraktes som delt som,

K m c q e t g

Den tredje samtalen er:

Conquer (arr, 4, 4, 5);

Det er Conquer Call for de to underlistene: E og T: Den første underlisten bestående av ett element, og den andre underlisten som består av ett element. Conquer () -metoden smelter sammen og sorterer to underlister. Den resulterende underlisten ville være e g . Hele listen ville bli:

K m q c e t g

Selv om e t -sekvensen forblir den samme, var du beskjed om at sortering har funnet sted, selv om den endelige typen fremdeles kommer.

Husk at det fremdeles er metoder som ble bemerket og reservert. De kalles omvendt rekkefølge. De vil nå bli kalt fra og med,

del (arr, 5, 6);

Merk at den nye sluttindeksen er 6, som er slutten på den nye høyre halvdelen. Midindeksen er nå 5 = (5 + 6) / 2 (heltall aritmetikk). Metoden ringer, deres orden og argumenter blir,

del (arr, 5, 5);
del (arr, 6, 6);
Conquer (arr, 5, 5, 6);

De to første samtalene mislykkes fordi de adresserer underlister med enkeltelement. På dette tidspunktet er hele listen:

K m q c e t g

Neste samtale er:

Conquer (arr, 5, 5, 6);

Det er Conquer Call for de to underlistene: T og G: Den første underlisten bestående av ett element, og den andre underlisten som består av ett element. Conquer () -metoden smelter sammen og sorterer to underlister. Den resulterende underlisten ville være G t . Hele listen ville bli:

K m q c e g t

Husk at det fremdeles er metoder som ble bemerket og reservert. De kalles omvendt rekkefølge. Den neste som skal kalles er,

Conquer (arr, 0, 1, 3);

Det er Conquer Call for de to underlistene: K M og Q C: Den første underlisten bestående av to elementer, og den andre underlisten bestående av to elementer. Conquer () -metoden smelter sammen og sorterer to underlister. Den resulterende underlisten ville være C k m q. Hele listen ville bli:

C k m q e g t

En annen Conquer () -metode som ble bemerket og reservert er:

Conquer (arr, 4, 5, 6);

Det er Conquer Call for de to underlistene: E G og T. Conquer () -metoden smelter sammen og sorterer to underlister. Den resulterende underlisten ville være e g t. Hele listen ville bli:

C k m q e g t

Den siste erobreren () samtalen som er bemerket og reservert er:

Conquer (arr, 0, 3, 6);

Det er Conquer Call for de to underlistene: C K M Q og E G T: Den første underlisten bestående av fire elementer, og den andre underlisten bestående av tre elementer. Conquer () -metoden smelter sammen og sorterer to underlister. Den resulterende underlisten ville være c e g k m q t, som er hele underlisten, det vil si:

C e g k m q t

Og det avslutter sammenslåing og sortering.

Conquer () -metoden

Conquer-metoden smelter sammen og sorterer to underlister. En underliste består av minst en verdi. Conquerer-metoden tar som argument, den opprinnelige matrisen, begynnelsesindeksen for den første underlisten, midtindeksen for de to påfølgende underlisten sett sammen, og sluttindeksen for den andre underlisten. Conquer -metoden har en midlertidig matrise, hvis lengde er den av den opprinnelige matrisen. Koden for Conquer -metoden er:

void conquerer (char arr [], int teg, int midt, int end)
int i = tig, j = mid+1, k = tig, indeks = tig;
char temp [] = ny røye [7];
mens jeg<=mid && j<=end)
if (arr [i]temp [indeks] = arr [i];
i = i+1;

annet
temp [indeks] = arr [j];
j = j+1;

indeks ++;

if (i> midt)
mens (j<=end)
temp [indeks] = arr [j];
indeks ++;
J ++;


annet
mens jeg<=mid)
temp [indeks] = arr [i];
indeks ++;
i ++;


k = tigge;
mens (karr [k] = temp [k];
K ++;

Hovedmetoden er:

public static void main (String [] args)
char arr [] = 'm', 'k', 'q', 'c', 'e', ​​'t', 'g';
THECLASS FERGESORT = NYTT THECLASS ();
sammenslåing.del (arr, 0,6);
System.ute.println ("de sorterte elementene:");
for (int i = 0; i<7;i++)
System.ute.print (arr [i]); System.ute.skrive ut(");

System.ute.println ();

Divide () -metoden, Conquer () -metoden og Main () -metoden skal kombineres til en klasse. Utgangen er:

C e g k m q t

Som forventet.

Midlertidig matrise for Conquer () -metoden

Når underlisteparene er sortert, holdes resultatet i den midlertidige matrisen, temp []. Arrangementet av verdier i den midlertidige matrisen erstatter til slutt innholdet i den opprinnelige matrisen. Følgende viser arrangementet i den opprinnelige matrisen og den for den midlertidige matrisen for de forskjellige samtalene til Conquer () -metoden:

Conquer (arr, 0, 0, 1);
arr [7]: m k q c e t g
Temp [7]: K m - - - - -
Conquer (arr, 2, 2, 3);
arr [7]: k m q c e t g
Temp [7]: K M C Q - - -
Conquer (arr, 4, 4, 5);
arr [7]: k m c q e t g
temp [7]: k m c q e t -
Conquer (arr, 5, 5, 6);
arr [7]: k m c q e t g
temp [7]: k m c q e g t
Conquer (arr, 0, 1, 3);
arr [7]: k m c q e g t
temp [7]: c k m q e g t
Conquer (arr, 4, 5, 6);
arr [7]: c k m q e g t
temp [7]: c k m q e g t
Conquer (arr, 0, 3, 6);
arr [7]: c k m q e g t
temp [7]: c e g k m q t

Konklusjon

Merge -sort er et sorteringsskjema som bruker skillet og erobrer paradigmet. Den deler en liste over elementer i enkeltelementer og begynner deretter å bringe påfølgende par underlister sammen, sortert, som begynner fra underlistene for enkeltelementet. Divide and Conquer Prosedyrer blir sammen gjort rekursivt. Denne opplæringen har forklart hvordan det gjøres i Java.

Chrys