Deze blog is gebaseerd op de verdeel en heersbenadering. Merge Sort is een 'verdeel en heers' -algoritme waarbij het probleem wordt onderverdeeld in subproblemen en vervolgens wordt samengevoegd om de oplossing te overwinnen. Deze blog over Samenvoegen Sorteren in zal u in detail door de onderstaande onderwerpen leiden -
hoe semaforen in java te gebruiken
- Wat is samenvoegsortering in Python?
- De verdeel en heers-aanpak
- Merge Sort implementeren in Python
- Stroomschema voor implementatie van Merge Sort
- Voordelen en gebruik
Wat is samenvoegsortering in Python?
Samenvoegen Sorteren is gebaseerd op het verdeel en heers-algoritme waarbij de invoerarray in twee helften wordt verdeeld, vervolgens afzonderlijk wordt gesorteerd en weer wordt samengevoegd om de oplossing te bereiken. De functie merge () wordt gebruikt voor het samenvoegen van de gesorteerde .
De verdeel en heers-aanpak
- De array wordt in tweeën gedeeld en het proces wordt herhaald met elke helft totdat elke helft de grootte 1 of 0 heeft.
- De reeks van grootte 1 is triviaal gesorteerd.
- Nu worden de twee gesorteerde arrays gecombineerd tot één grote array. En dit wordt voortgezet totdat alle elementen zijn gecombineerd en de array is gesorteerd.
Hier is een visualisatie van de samenvoegsortering om de afbeelding voor u te wissen
Invoerarray = [3,1,4,1,5,9,2,6,5,4]
Laten we nu verder gaan met de implementatie.
Merge Sort implementeren in Python
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (rechter helft) i = j = k = 0 terwijl ik Uitgang:
$ python main.py
(‘Splitsen’, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(‘Splitsen’, [3, 1, 4, 1, 5])
(‘Splitsen’, [3, 1])
(‘Splitsen’, [3])
(‘Samenvoegen‘, [3])
(‘Splitsen’, [1])
(‘Samenvoegen‘, [1])
(‘Samenvoegen‘, [1, 3])
(‘Splitsen’, [4, 1, 5])
(‘Splitsen’, [4])
(‘Samenvoegen‘, [4])
(‘Splitsen’, [1, 5])
(‘Splitsen’, [1])
(‘Samenvoegen‘, [1])
(‘Splitsen’, [5])
(‘Samenvoegen‘, [5])
(‘Samenvoegen‘, [1, 5])
(‘Samenvoegen‘, [1, 4, 5])
(‘Samenvoegen‘, [1, 1, 3, 4, 5])
(‘Splitsen’, [9, 2, 6, 5, 4])
(‘Splitsen’, [9, 2])
(‘Splitsen’, [9])
(‘Samenvoegen‘, [9])
(‘Splitsen’, [2])
(‘Samenvoegen‘, [2])
(‘Samenvoegen‘, [2, 9])
(‘Splitsen’, [6, 5, 4])
(‘Splitsen’, [6])
(‘Samenvoegen‘, [6])
(‘Splitsen’, [5, 4])
(‘Splitsen’, [5])
(‘Samenvoegen‘, [5])
(‘Splitsen’, [4])
(‘Samenvoegen‘, [4])
(‘Samenvoegen‘, [4, 5])
(‘Samenvoegen‘, [4, 5, 6])
(‘Samenvoegen‘, [2, 4, 5, 6, 9])
(‘Samenvoegen‘, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
sql server tutorial voor beginners
Stroomschema voor de implementatie van Merge Sort
Voordelen en gebruik van samenvoegsortering
De meeste andere algoritmen presteren slecht met opeenvolgende datastructuren zoals bestanden en gekoppelde lijsten. In deze structuren kost toegang tot een willekeurig element lineaire tijd, niet een regelmatige constante tijd. En de aard van het samenvoegen maakt het gemakkelijk en snel voor dergelijke gegevensstructuren.Een van de beste kenmerken van samenvoegsortering is het lage aantal vergelijkingen. Het maakt O (n * log (n)) aantal vergelijkingen, maar de constante factor is goed in vergelijking met quicksort, wat het nuttig maakt wanneer de vergelijkingsfunctie een langzame bewerking is.Ook maakt de verdeel-en-heersbenadering van samenvoegsortering het handig voor parallelle verwerking.
Hiermee komen we aan het einde van deze blog over “Hoe Merge Sort in Python te implementeren”. Ik hoop dat de inhoud wat waarde heeft toegevoegd aan je kennis in Python. Om diepgaande kennis op te doen over Python en de verschillende applicaties, kunt u zich live inschrijven met 24/7 ondersteuning en levenslange toegang.