Hvordan implementere en fusjonssort i Java

I Java -programmering kan det være tilfeller der utvikleren trenger å sortere bulkoppføringene. For eksempel å ordne eller analysere de tilfeldig genererte verdiene. I slike tilfeller "Slå sammen”I Java er effektiv og raskere, og bruker dermed mindre tid til å sortere de lengre oppføringene eller listene sammenlignet med andre algoritmer i.e., “Boble sort”.

Denne bloggen vil utdype implementeringen av "Merge Sort" -algoritmen i Java.

Hvordan implementere en "Merge -sort" i Java?

“Slå sammen”Er basert på“splitt og hersk”Algoritme slik at matrisen er delt inn i like halvdeler og deretter videre underinndelt til divisjonen ikke lenger kan gjøres. Etter at matrisen er inndelt, blir den slått sammen basert på elementene på en sortert (stigende) måte.

Demonstrasjon av "Merge Sort" -algoritmen

La oss oversikt over den undervernede koden for å forstå det diskuterte konseptet:

offentlig klasse fusjonerer
Offentlig statisk tomrom MergedArray (int [] LeftArray, Int [] RightArray, Int [] FinalArray, Int LeftArraysize, Int RightArraysize)
int element = 0, venstre = 0, høyre = 0;
mens (til venstreif (venstrearray [til venstre]finalArray [element ++] = venstreArray [venstre ++];

ellers
finalArray [element ++] = RightArray [Right ++];

mens (til venstrefinalArray [element ++] = venstreArray [venstre ++];

mens (til høyrefinalArray [element ++] = RightArray [Right ++];

I ovennevnte kode som er tildelt for sammenslåing, bruk følgende trinn:

• • Definere en funksjon som heter “sammenslåing”Å ha de uttalte parametrene for henholdsvis venstre og høyre matriser, den opprinnelige matrisen og størrelsene på venstre og høyre matriser.
  • I funksjonsdefinisjonen, initialiser de uttalte verdiene for å bruke en tilstand senere i koden.
  • I neste trinn, bruk kombinert “samtidig som”Loop og“hvis”Tilstand for å sjekke tilstanden for sammenslåing.
  • Det er slik at hvis elementet i venstre matrise er mindre enn det for høyre array -element ved en bestemt indeks, så blir den sammenslåtte arrayen lagt ved venstre array -element fra venstre til høyre.
  • I det andre tilfellet er det høyre arrayelementet vedlagt.
  • Etter det, bruk "samtidig som”Loop for å sjekke om bare elementer i venstre eller høyre matrise er igjen og legg dem til matrisen deretter.

Gjennomføring

La oss nå gå videre til følgende kodebit:

public static void DIILEARRAY (int [] matrise, int -lengde)
hvis (lengde < 2)return;
int div = lengde / 2;
int [] larray = new int [div];
int [] rarray = new int [lengde-div];
int temp = 0;
for (int i = 0; iif (ilarray [i] = array [i];

ellers
rarray [temp] = array [i];
temp = temp+1;

DIILEARRAY (Larray, Div);
DIILEARRAY (rarray, lengde-div);
MergedArray (Larray, Rarray, Array, Div, Lengde-Div);

I denne koden implementert for å dele den beståtte matrisen, utfør trinnene under levert:

• • Definere funksjonen “DIAREARRAY ()”Å ha parametrene som peker på den passerte matrisen og dens lengde.
  • Nå, sjekk for tilstanden slik at matriselengden ikke er større enn “2”. I så fall kan du returnere matrisen som den er. Ellers, utfør de videre funksjonalitetene.
  • Etter det, del matrisen i to like halvdeler via dens (matrisen) passerte lengde.
  • I neste trinn, lag to heltallsarrayer basert på den delte lengden på den passerte matrisen.
  • Nå, legg til venstre og høyre delte matriser med de passerte arrayelementene.
  • Til slutt, påkaller denne funksjonen rekursivt på disse to delte matriser som akkumulerer de kopierte dataene fra den opprinnelige passerte matrisen, og får tilgang til "MergedArray ()”Funksjon som sammenligner og sorterer venstre og høyre matriser.

Gjennomføring

Nå, oversikt over "hoved-”Kode:

public static void main (String args [])
int [] MergeSortArray = 30, 12, 46, 6, 17, 23;
DIILEARRAY (MergesortArray, MergesortArray.lengde);
for (int i = 0; i< mergesortArray.length;++i)
System.ute.print (MergeSortArray [i]+ "");

I “hoved-”, Bruk følgende trinn:

• • Erklære en matrise som heter “Fusjonsortarray”Det må sorteres.
  • I neste trinn, påkalle funksjonen "DIAREARRAY ()”Ved å passere den deklarerte matrisen og dens lengde via“lengde”Eiendom, som henholdsvis dens argumenter.
  • Etter det, itererer du gjennom matrisen og viser de sorterte matriseelementene via “til" Løkke.
  • Algoritme: Den medfølgende matrisen vil bli sendt til funksjonen “DIAREARRAY ()”Som deler matrisen, og denne funksjonen påkaller deretter funksjonen”MergedArray ()”Som fusjonerer de delte matriser basert på de inneholdte elementene.

Gjennomføring

Hele koden

offentlig klasse fusjonerer
Offentlig statisk tomrom MergedArray (int [] LeftArray, Int [] RightArray, Int [] FinalArray, Int LeftArraysize, Int RightArraysize)
int element = 0, venstre = 0, høyre = 0;
mens (til venstreif (venstrearray [til venstre]finalArray [element ++] = venstreArray [venstre ++];

ellers
finalArray [element ++] = RightArray [Right ++];

mens (til venstrefinalArray [element ++] = venstreArray [venstre ++];

mens (til høyrefinalArray [element ++] = RightArray [Right ++];

public static void DIILEARRAY (int [] matrise, int -lengde)
hvis (lengde < 2)return;
int div = lengde / 2;
int [] larray = new int [div];
int [] rarray = new int [lengde-div];
int temp = 0;
for (int i = 0; iif (ilarray [i] = array [i];

ellers
rarray [temp] = array [i];
temp = temp+1;

DIILEARRAY (Larray, Div);
DIILEARRAY (rarray, lengde-div);
MergedArray (Larray, Rarray, Array, Div, Lengde-Div);

public static void main (String args [])
int [] MergeSortArray = 30, 12, 46, 6, 17, 23;
DIILEARRAY (MergesortArray, MergesortArray.lengde);
for (int i = 0; i< mergesortArray.length;++i)
System.ute.print (MergeSortArray [i]+ "");

Produksjon

I denne utgangen kan det antydes at den passerte matrisen er sortert på riktig måte.

Konklusjon

Merge -sorteringen er basert på “splitt og hersk”Algoritme slik at matrisen er delt inn i like halvdeler og slår seg sammen igjen basert på de sorterte elementene. Utfallet av algoritmen hentes i samsvar med den originale på en sortert måte. Denne bloggen diskuterte implementeringen av Merge Sort -algoritmen i Java.