Sorteer samenvoegen in C ++ met voorbeelden

merge sort c with examples

C ++ Sorteertechniek samenvoegen.

Het samenvoegingsalgoritme maakt gebruik van de verdeel en heers ”Strategie waarin we het probleem opdelen in deelproblemen en die deelproblemen afzonderlijk oplossen.

Deze subproblemen worden vervolgens gecombineerd of samengevoegd om een ​​uniforme oplossing te vormen.

​ Lees hier de populaire C ++ trainingsserie.

Wat je leert:

• Overzicht
• Algemeen algoritme
• Pseudo-code voor samenvoegsortering
• Illustratie
• Iteratieve samenvoegsortering
• Complexiteitsanalyse van het samenvoegsorteeralgoritme
• Gevolgtrekking
• Aanbevolen literatuur

Overzicht

Samenvoegsortering wordt uitgevoerd met behulp van de volgende stappen:

# 1) De te sorteren lijst wordt verdeeld in twee arrays van gelijke lengte door de lijst te verdelen over het middelste element. Als het aantal elementen in de lijst 0 of 1 is, wordt de lijst als gesorteerd beschouwd.

#twee) Elke sublijst wordt afzonderlijk gesorteerd door recursief samenvoegsortering te gebruiken.

# 3) De gesorteerde sublijsten worden vervolgens gecombineerd of samengevoegd om een ​​complete gesorteerde lijst te vormen.

Algemeen algoritme

De algemene pseudo-code voor de merge sort-techniek wordt hieronder gegeven.

beste anti-spyware voor Windows 7

Declareer een array Arr met lengte N
Als N = 1, is Arr al gesorteerd
Als N> 1,
Links = 0, rechts = N-1
Zoek midden = (links + rechts) / 2
Call merge_sort (Arr, left, middle) => sorteer de eerste helft recursief
Roep merge_sort (Arr, midden + 1, rechts) => sorteer tweede helft recursief
Oproep samenvoegen (Arr, links, midden, rechts) om gesorteerde arrays in bovenstaande stappen samen te voegen.
Uitgang

Zoals getoond in de bovenstaande pseudocode, verdelen we in het samenvoegsorteeralgoritme de array in tweeën en sorteren we elke helft met recursief samenvoegsortering. Zodra sub-arrays afzonderlijk zijn gesorteerd, worden de twee sub-arrays samengevoegd om een ​​volledig gesorteerde array te vormen.

Pseudo-code voor samenvoegsortering

Hieronder volgt de pseudocode voor de samenvoegsorteertechniek. Ten eerste hebben we een procedure voor het samenvoegen van sorteren om de array recursief in twee helften te splitsen. Dan hebben we een samenvoegroutine die de gesorteerde kleinere arrays zal samenvoegen om een ​​volledig gesorteerde array te krijgen.

Laten we nu de samenvoegsorteertechniek met een voorbeeld illustreren.

Illustratie

De bovenstaande afbeelding kan hieronder in tabelvorm worden weergegeven:

Zoals weergegeven in de bovenstaande weergave, wordt de array eerst verdeeld in twee sub-arrays van lengte 4. Elke sub-array wordt verder onderverdeeld in nog twee sub-arrays van lengte 2. Elke sub-array wordt vervolgens verder onderverdeeld in een sub-array. van elk een element. Dit hele proces is het 'Verdeel' -proces.

Nadat we de array hebben opgedeeld in sub-arrays van elk afzonderlijk element, moeten we deze arrays nu in gesorteerde volgorde samenvoegen.

Zoals te zien is in de bovenstaande illustratie, beschouwen we elke subarray van een enkel element en combineren we eerst de elementen om sub-arrays van twee elementen in gesorteerde volgorde te vormen. Vervolgens worden de gesorteerde subarrays met lengte twee gesorteerd en gecombineerd om twee subarrays met lengte vier elk te vormen. Vervolgens combineren we deze twee sub-arrays om een ​​compleet gesorteerde array te vormen.

Iteratieve samenvoegsortering

Het algoritme of de techniek van samenvoegen die we hierboven hebben gezien, gebruikt recursie. Het is ook bekend als ' recursieve samenvoegsortering ​

We weten dat recursieve functies functieaanroepstapel gebruiken om de tussenliggende status van de aanroepfunctie op te slaan. Het slaat ook andere boekhoudkundige informatie op voor parameters enz. En brengt overhead met zich mee in termen van het opslaan van activeringsrecords van het oproepen van de functie en het hervatten van de uitvoering.

Al deze overheadkosten kunnen worden weggenomen als we iteratieve functies gebruiken in plaats van recursieve. Het bovenstaande samenvoegsorteeralgoritme kan ook eenvoudig worden omgezet in iteratieve stappen met behulp van lussen en besluitvorming.

Net als recursieve samenvoegsortering, heeft iteratieve samenvoegsortering ook O (nlogn) -complexiteit, dus qua prestaties presteren ze op gelijke voet met elkaar. We kunnen de overhead eenvoudigweg verlagen.

In deze tutorial hebben we ons geconcentreerd op recursieve samenvoegsortering en vervolgens zullen we recursieve samenvoegsortering implementeren met behulp van C ++ en Java-talen.

Hieronder wordt een implementatie gegeven van de samenvoegsorteertechniek met behulp van C ++.

Uitgang:

Voer het aantal te sorteren elementen in: 10

Voer 10 te sorteren elementen in: 101 10 2 43 12 54 34 64 89 76

Gesorteerde array

2 10 12 34 43 54 64 76 89101

In dit programma hebben we twee functies gedefinieerd, merge_sort en Gaan ​In de merge_sort-functie verdelen we de array in twee gelijke arrays en roepen we de merge-functie aan op elk van deze sub-arrays. In de samenvoegfunctie doen we de daadwerkelijke sortering op deze subarrays en voegen ze vervolgens samen tot één compleet gesorteerde array.

Vervolgens implementeren we de Merge Sort-techniek in Java-taal.

Uitgang:

Invoerarray

101 10 2 43 12 54 34 64 89 76

Array gesorteerd met samenvoegsortering

2 10 12 34 43 54 64 76 89101

Ook bij de Java-implementatie gebruiken we dezelfde logica als bij de C ++ -implementatie.

Samenvoegen is een efficiënte manier om lijsten te sorteren en wordt meestal gebruikt voor het sorteren van gekoppelde lijsten. Omdat het een verdeel-en-heersbenadering gebruikt, werkt de sorteertechniek voor samenvoegen even efficiënt voor zowel kleinere als grotere arrays.

Complexiteitsanalyse van het samenvoegsorteeralgoritme

We weten dat als we sorteren met samenvoegsortering willen uitvoeren, we de array eerst in twee gelijke helften verdelen. Dit wordt weergegeven door 'log n', wat een logaritmische functie is en het aantal genomen stappen is maximaal log (n + 1).

Om het middelste element van de array te vinden, hebben we een enkele stap nodig, d.w.z. O (1).

Om de sub-arrays vervolgens samen te voegen tot een array van n elementen, nemen we O (n) hoeveelheid looptijd.

De totale tijd voor het uitvoeren van een samenvoegsortering is dus n (log n + 1), wat ons de tijdcomplexiteit van O (n * logn) geeft.

De tijdcomplexiteit voor samenvoegsortering is in alle drie de gevallen (slechtste, beste en gemiddelde) hetzelfde, aangezien het de array altijd in sub-arrays verdeelt en vervolgens de sub-arrays samenvoegt met lineaire tijd.

Samenvoegsortering neemt altijd evenveel ruimte in beslag als ongesorteerde arrays. Als de lijst die moet worden gesorteerd een array is, mag de samenvoegsortering dus niet worden gebruikt voor zeer grote arrays. Samenvoegsortering kan echter effectiever worden gebruikt voor het sorteren van gekoppelde lijsten.

Gevolgtrekking

Samenvoegen sorteren maakt gebruik van de 'verdeel en heers' -strategie die de array of lijst opsplitst in talrijke sub-arrays en ze afzonderlijk sorteert en vervolgens samenvoegt tot een compleet gesorteerde array.

Samenvoegen sorteren werkt sneller dan andere sorteermethoden en werkt ook efficiënt voor kleinere en grotere arrays.

We zullen meer ontdekken over Snel sorteren in onze aanstaande tutorial!

​ Bekijk hier de Beginners C ++ Trainingsgids.

Aanbevolen literatuur

• MongoDB Sort () -methode met voorbeelden
• Unix-sorteeropdracht met syntaxis, opties en voorbeelden
• Shell-sortering in C ++ met voorbeelden
• Heap-sortering in C ++ met voorbeelden
• Selectie sorteren in C ++ met voorbeelden
• Bubbelsortering in C ++ met voorbeelden
• Invoegsortering in C ++ met voorbeelden
• Snel sorteren in C ++ met voorbeelden