merge sort java program implement mergesort
Deze tutorial legt uit wat Merge Sort in Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Voorbeelden van Iterative & Recursive MergeSort is:
De sorteertechniek voor samenvoegen maakt gebruik van een 'Verdeel-en-Heers' -strategie. Bij deze techniek wordt de te sorteren dataset opgedeeld in kleinere eenheden om deze te sorteren.
Lees de Easy Java Training Series door.
Wat je leert:
- Sorteren samenvoegen in Java
- Gevolgtrekking
Sorteren samenvoegen in Java
Bijvoorbeeld, als een array moet worden gesorteerd met behulp van mergesort, dan wordt de array rond zijn middelste element in twee sub-arrays verdeeld. Deze twee sub-arrays worden verder onderverdeeld in kleinere eenheden totdat we slechts 1 element per eenheid hebben.
Zodra de deling is voltooid, voegt deze techniek deze individuele eenheden samen door elk element te vergelijken en ze te sorteren bij het samenvoegen. Op deze manier krijgen we tegen de tijd dat de hele array weer is samengevoegd een gesorteerde array.
In deze tutorial bespreken we alle details van deze sorteertechniek in het algemeen, inclusief het algoritme en de pseudocodes, evenals de implementatie van de techniek in Java.
MergeSort-algoritme in Java
Hieronder volgt het algoritme voor de techniek.
# 1) Declareer een array myArray met de lengte N
#twee) Controleer of N = 1, myArray is al gesorteerd
# 3) Als N groter is dan 1,
- set links = 0, rechts = N-1
- bereken midden = (links + rechts) / 2
- Roep subroutine merge_sort (myArray, left, middle) => dit sorteert de eerste helft van de array
- Roep subroutine merge_sort (myArray, middle + 1, right) => dit sorteert de tweede helft van de array
- Roep subroutine merge aan (myArray, left, middle, right) om arrays samen te voegen die in de bovenstaande stappen zijn gesorteerd.
# 4) Uitgang
Zoals te zien is in de algoritmestappen, is de array in het midden in tweeën gedeeld. Vervolgens sorteren we recursief de linkerhelft van de array en vervolgens de rechterhelft. Zodra we beide helften afzonderlijk hebben gesorteerd, worden ze samengevoegd om een gesorteerde array te verkrijgen.
Sorteer pseudo-code samenvoegen
Laten we eens kijken naar de pseudo-code voor de Mergesort-techniek. Zoals reeds besproken, aangezien dit een ‘verdeel-en-heers'-techniek is, zullen we de routines presenteren voor het verdelen van de dataset en vervolgens het samenvoegen van de gesorteerde datasets.
In de bovenstaande pseudo-code hebben we twee routines, namelijk Mergesort en merge. De routine Mergesort splitst de invoerarray op in een individuele array die gemakkelijk genoeg te sorteren is. Vervolgens wordt de samenvoegroutine genoemd.
De samenvoegroutine voegt de individuele sub-arrays samen en retourneert een resulterende gesorteerde array. Nu we het algoritme en de pseudo-code voor het samenvoegen hebben gezien, laten we deze techniek nu illustreren aan de hand van een voorbeeld.
MergeSort illustratie
Beschouw de volgende array die met deze techniek moet worden gesorteerd.
Volgens het samenvoegingsalgoritme splitsen we deze array in het middenelement in twee sub-arrays. Daarna gaan we door met het splitsen van de sub-arrays in kleinere arrays totdat we een enkel element in elke array krijgen.
Zodra elke sub-array slechts één element bevat, voegen we de elementen samen. Tijdens het samenvoegen vergelijken we de elementen en zorgen we ervoor dat ze in de samengevoegde array op orde zijn. Dus werken we onze weg omhoog om een samengevoegde array te krijgen die is gesorteerd.
Het proces wordt hieronder weergegeven:
Zoals te zien is in de bovenstaande illustratie, zien we dat de array herhaaldelijk wordt verdeeld en vervolgens wordt samengevoegd om een gesorteerde array te krijgen. Met dit concept in gedachten, gaan we verder met de implementatie van Mergesort in de programmeertaal Java.
Sorteerimplementatie samenvoegen in Java
We kunnen de techniek in Java implementeren met behulp van twee benaderingen.
Iteratieve samenvoegsortering
Dit is een benadering van onderop. De sub-arrays van elk één element worden gesorteerd en samengevoegd om arrays met twee elementen te vormen. Deze arrays worden vervolgens samengevoegd om arrays met vier elementen te vormen, enzovoort. Op deze manier wordt de gesorteerde array opgebouwd door omhoog te gaan.
Het onderstaande Java-voorbeeld toont de iteratieve Merge Sort-techniek.
Uitgang:
Oorspronkelijke matrix: (10, 23, -11, 54, 2, 9, -10, 45)
Gesorteerde matrix: (-11, -10, 2, 9, 10, 23, 45, 54)
Recursieve samenvoegsortering
Dit is een top-down benadering. Bij deze benadering wordt de te sorteren array opgesplitst in kleinere arrays totdat elke array slechts één element bevat. Dan wordt het sorteren eenvoudig uit te voeren.
De volgende Java-code implementeert de recursieve benadering van de sorteertechniek samenvoegen.
Uitgang:
Oorspronkelijke matrix: (10, 23, -11, 54, 2, 9, -10, 45)
Gesorteerde array: (- 11, -10, 2, 9, 10, 23, 45, 54)
Laten we in de volgende sectie overschakelen van arrays en de techniek gebruiken om de datastructuren van de gekoppelde lijst en de arraylijst te sorteren.
Sorteer gekoppelde lijst met samenvoegsortering in Java
Mergesort-techniek heeft de meeste voorkeur voor het sorteren van gekoppelde lijsten. Andere sorteringstechnieken presteren slecht als het gaat om de gelinkte lijst vanwege de veelal sequentiële toegang.
Het volgende programma sorteert een gekoppelde lijst met behulp van deze techniek.
Uitgang:
Oorspronkelijke gekoppelde lijst:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Gesorteerde gekoppelde lijst:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null
welke site een recensie geeft over software voor het opschonen van registers
Sorteer ArrayList met samenvoegsortering in Java
Net als Arrays en Linked Lists kunnen we deze techniek ook gebruiken voor het sorteren van een ArrayList. We zullen vergelijkbare routines gebruiken om de ArrayList recursief te verdelen en vervolgens de sublijsten samen te voegen.
De onderstaande Java-code implementeert de Merge-sorteertechniek voor ArrayList.
Uitgang:
Originele ArrayList:
17 40 36 7 6 23 35 2 38
Gesorteerde ArrayList:
2 6 7 17 23 35 36 38 40
Veel Gestelde Vragen
V # 1) Kan sortering samenvoegen zonder recursie?
Antwoord: Ja. We kunnen een niet-recursieve samenvoegsortering uitvoeren met de naam ‘iteratieve samenvoegsortering’. Dit is een bottom-up benadering die begint met het samenvoegen van sub-arrays met een enkel element tot een sub-array van twee elementen.
Vervolgens worden deze sub-arrays met 2 elementen samengevoegd tot sub-arrays met 4 elementen en zo verder met iteratieve constructies. Dit proces gaat door totdat we een gesorteerde array hebben.
Vraag 2 Kan sortering samenvoegen op zijn plaats worden uitgevoerd?
Antwoord: Samenvoegsortering is over het algemeen niet aanwezig. Maar we kunnen het ter plaatse maken door een slimme implementatie te gebruiken. Bijvoorbeeld, door twee elementenwaarde op één positie op te slaan. Dit kan achteraf worden geëxtraheerd met behulp van modulus en deling.
Vraag 3 Wat is een sortering voor samenvoegen in drie richtingen?
Antwoord: De techniek die we hierboven hebben gezien, is een 2-way Merge-sortering waarbij we de te sorteren array in twee delen splitsen. Vervolgens sorteren en samenvoegen we de array.
In een 3-way Merge-sortering, in plaats van de array in 2 delen te splitsen, splitsen we het in 3 delen, sorteren we het en voegen het uiteindelijk samen.
Vraag 4 Wat is de tijdcomplexiteit van Mergesort?
Antwoord: De totale tijdcomplexiteit van het samenvoegen in alle gevallen is O (nlogn).
Q # 5) Waar wordt de sortering Samenvoegen gebruikt?
Antwoord: Het wordt meestal gebruikt bij het sorteren van de gekoppelde lijst in O (nlogn) tijd. Het wordt ook gebruikt in gedistribueerde scenario's waarin nieuwe gegevens in het systeem binnenkomen vóór of na het sorteren. Dit wordt ook gebruikt in verschillende databasescenario's.
Gevolgtrekking
Samenvoegsortering is een stabiele sortering en wordt uitgevoerd door de dataset eerst herhaaldelijk in subsets te splitsen en vervolgens deze subsets te sorteren en samen te voegen om een gesorteerde dataset te vormen. De dataset wordt gesplitst totdat elke dataset triviaal en gemakkelijk te sorteren is.
We hebben de recursieve en iteratieve benaderingen van de sorteertechniek gezien. We hebben ook het sorteren van de datastructuur Linked List en ArrayList met Mergesort besproken.
We zullen doorgaan met de bespreking van meer sorteertechnieken in onze komende tutorials. Blijf kijken!
Bezoek hier voor de exclusieve Java Training Tutorial Series.
Aanbevolen literatuur
- Sorteer samenvoegen in C ++ met voorbeelden
- Hoe een array in Java te sorteren - Tutorial met voorbeelden
- Bubbelsortering in Java - Java-sorteeralgoritmen en codevoorbeelden
- Selectie sorteren in Java - Selectie sorteeralgoritme en voorbeelden
- Invoegsortering in Java - Invoegsorteeralgoritme en voorbeelden
- QuickSort in Java - Algoritme, illustratie en implementatie
- Arrays in Java 8 - Stream Class en ParallelSort-methode
- Inleiding tot sorteertechnieken in C ++