Inleiding

soms kunnen gegevens die we opslaan of ophalen in een toepassing weinig of geen volgorde hebben. Het kan zijn dat we de gegevens moeten herschikken om ze correct te verwerken of efficiënt te gebruiken. In de loop der jaren hebben computerwetenschappers vele sorteeralgoritmen gecreëerd om gegevens te organiseren.

In dit artikel zullen we een kijkje nemen op populaire sorteeralgoritmen, begrijpen hoe ze werken en ze coderen in Python. We zullen ook vergelijken hoe snel ze items sorteren in een lijst.,

voor de eenvoud zouden algoritme-implementaties lijsten met getallen in oplopende volgorde sorteren., Natuurlijk kunt u ze aanpassen aan uw behoeften

als u meer wilt weten over een specifiek algoritme, kunt u hier naar toe springen:

• Bubble Sorteer
• selectie Sorteer
• invoegen Sorteer
• Heap Sorteer
• snelle Sorteer
• sorteren in Python

Bubble Sorteer

Dit eenvoudige sorteeralgoritme itereert over een lijst, vergelijkt elementen in paren en wisselt ze totdat de grotere elementen “opborrelen” naar het einde van de lijst, en de kleinere elementen aan de “onderkant”blijven.,

uitleg

we beginnen met het vergelijken van de eerste twee elementen van de lijst. Als het eerste element groter is dan het tweede element, wisselen we ze om. Als ze al in orde zijn, laten we ze zoals ze zijn. We gaan dan naar het volgende paar elementen, vergelijken hun waarden en wisselen waar nodig. Dit proces gaat door tot het laatste paar items in de lijst.

na het bereiken van het einde van de lijst, herhaalt het dit proces voor elk item. Hoewel, dit is zeer inefficiënt. Wat als er slechts een enkele swap moet worden gemaakt in de array?, Waarom zouden we nog steeds herhalen hoewel het n^2 keer, ook al is het al gesorteerd?

om het algoritme te optimaliseren, moeten we het natuurlijk stoppen als het klaar is met Sorteren, anders zal het een reeds gesorteerde array vele malen opnieuw evalueren.

hoe zouden we weten dat we klaar zijn met Sorteren? Als de items in orde waren dan zouden we niet hoeven te ruilen. Dus, wanneer we waarden wisselen zetten we een vlag op True om het sorteerproces te herhalen. Als er geen swaps plaatsvonden, zou de vlag False blijven en zal het algoritme stoppen.,

implementatie

met de optimalisatie kunnen we Bubble Sort in Python als volgt implementeren:

het algoritme draait in een while lus, alleen breken als er geen items worden verwisseld. We stellen in het begin swapped in op True om ervoor te zorgen dat het algoritme minstens één keer draait.

tijdscomplexiteit

In het slechtste scenario (wanneer de lijst in omgekeerde volgorde staat), zou dit algoritme elk item van de array moeten omwisselen., Onzeswapped vlag zou worden ingesteld opTrue bij elke iteratie.

daarom, als we n elementen in onze lijst hebben, zouden we n iteraties per item hebben – dus is de tijdcomplexiteit van Bubble Sort O(n^2).

Selection Sort

dit algoritme segmenteert de lijst in twee delen: gesorteerd en ongesorteerd. We verwijderen continu het kleinste element van het ongesorteerde segment van de lijst en voegen het toe aan het gesorteerde segment.,

uitleg

in de praktijk hoeven we geen nieuwe lijst aan te maken voor de gesorteerde elementen, wat we doen is het meest linkse deel van de lijst behandelen als het gesorteerde segment. Vervolgens zoeken we in de hele lijst naar het kleinste element en ruilen het om met het eerste element.

nu weten we dat het eerste element van de lijst gesorteerd is, krijgen we het kleinste element van de resterende items en ruilen het met het tweede element. Dit blijft zo tot het laatste punt van de lijst het nog te onderzoeken element is.,

implementatie

We zien dat alsi toeneemt, we minder items moeten controleren.

tijdcomplexiteit

We kunnen de tijdcomplexiteit gemakkelijk verkrijgen door de for lussen te onderzoeken in het selectie-sorteeralgoritme. Voor een lijst met n elementen, de buitenste lus itereert n keer.

de binnenste lus itereert n-1 Als i gelijk is aan 1, en dan n-2 Als i gelijk is aan 2 enzovoort.

het aantal vergelijkingen is (n - 1) + (n - 2) + ... + 1, wat de selectie een tijdscomplexiteit geeft van O(n^2).,

Insertion Sort

zoals selectie Sort, segmenteert dit algoritme de lijst in gesorteerde en ongesorteerde delen. Het herhaalt zich over het ongesorteerde segment, en voegt het element dat wordt bekeken in de juiste positie van de gesorteerde lijst.

uitleg

We gaan ervan uit dat het eerste element van de lijst gesorteerd is. We gaan dan naar het volgende element, laten we het xnoemen. Als x groter is dan het eerste element dat we laten zoals het is., Als x kleiner is, kopiëren we de waarde van het eerste element naar de tweede positie en stellen we het eerste element in op x.

als we naar de andere elementen van het ongesorteerde segment gaan, verplaatsen we continu grotere elementen in het gesorteerde segment naar de lijst totdat we een element tegenkomen dat kleiner is dan x of het einde van het gesorteerde segment bereiken, en dan plaatsen we x in de juiste positie.

Als u een gedetailleerd, speciaal artikel wilt lezen voor het sorteren van invoegtoepassingen, dan hebben we het voor u!,

implementatie

tijdscomplexiteit

In het slechtste geval wordt een array in omgekeerde volgorde gesorteerd. De buitenste for loop in de Invoegsorteerfunctie itereert altijd n-1 keer.

Heapsort

Dit populaire sorteeralgoritme, zoals de sorteer-en Selectiesoorten, segmenteert de lijst in gesorteerde en ongesorteerde delen. Het zet het ongesorteerde segment van de lijst om in een Heap-gegevensstructuur, zodat we efficiënt het grootste element kunnen bepalen.,

uitleg

we beginnen met het omzetten van de lijst in een Max Heap – een binaire boom waar het grootste element de root node is. Dan plaatsen we dat item aan het einde van de lijst. Vervolgens herbouwen we onze Max Heap die nu een waarde minder heeft, waardoor de nieuwe grootste waarde voor het laatste item van de lijst wordt geplaatst.

we herhalen dit proces van het bouwen van de heap totdat alle knooppunten zijn verwijderd.

Als u een gedetailleerd, speciaal artikel voor Heap Sort wilt lezen, dan hebben we u gedekt!,

implementatie

We maken een helper functie heapify om dit algoritme te implementeren:

tijdcomplexiteit

laten we eerst kijken naar de tijdcomplexiteit van de heapify functie. In het ergste geval is het grootste element nooit het root-element, dit veroorzaakt een recursieve aanroep naar heapify. Hoewel recursieve aanroepen angstaanjagend duur lijken, bedenk dan dat we werken met een binaire boom.

visualiseer een binaire boom met 3 elementen, het heeft een hoogte van 2., Visualiseer nu een binaire boom met 7 elementen, het heeft een hoogte van 3. De boom groeit logaritmisch tot n. de functie heapify doorkruist die boom in o(log(n)) tijd.

de heap_sort functie itereert over de array n keer. Daarom is de totale tijdscomplexiteit van het Heapsorteeralgoritme O (nlog (n)).

samenvoegen Sorteer

Dit verdeel en heers algoritme splitst een lijst in de helft, en blijft de lijst splitsen door 2 totdat het enkelvoud elementen bevat.,

aangrenzende elementen worden gesorteerde paren, dan worden gesorteerde paren samengevoegd en gesorteerd met andere paren. Dit proces gaat door totdat we een gesorteerde lijst krijgen met alle elementen van de ongesorteerde invoerlijst.

uitleg

we splitsen de lijst recursief in tweeën totdat we lijsten met grootte één hebben. We mergen vervolgens elke helft die werd gesplitst, sorteren ze in het proces.

Sorteren wordt gedaan door de kleinste elementen van elke helft te vergelijken. Het eerste element van elke lijst is het eerste te vergelijken. Als de eerste helft begint met een kleinere waarde, dan voegen we dat toe aan de gesorteerde lijst., We vergelijken dan de tweede kleinste waarde van de eerste helft met de eerste kleinste waarde van de tweede helft.

elke keer dat we de kleinere waarde aan het begin van de helft selecteren, verplaatsen we de index waarvan het item met één moet worden vergeleken.

Als u een gedetailleerd, speciaal artikel wilt lezen voor Merge Sort, dan hebben we het voor u!

implementatie

merk op dat de merge_sort() functie, in tegenstelling tot de vorige sorteeralgoritmen, een nieuwe lijst retourneert die gesorteerd is, in plaats van de bestaande lijst te sorteren.,

daarom vereist samenvoegen ruimte om een nieuwe lijst te maken met dezelfde grootte als de invoerlijst.

tijdscomplexiteit

laten we eerst eens kijken naar de merge functie. Het neemt twee lijsten, en itereert n keer, waarbij n is de grootte van hun gecombineerde invoer.

de merge_sort functie splitst zijn gegeven array in 2, en sorteert de sub-arrays recursief. Aangezien de input die wordt recurseerd de helft is van wat er is gegeven, zoals binaire bomen maakt dit de tijd die nodig is om logaritmisch te groeien tot n.,

daarom is de totale tijdscomplexiteit van het Merge Sortalgoritme O (nlog (n)).

snelle sortering

dit verdeel en heers algoritme is het meest gebruikte sorteeralgoritme dat in dit artikel wordt behandeld. Wanneer correct geconfigureerd, Het is uiterst efficiënt en vereist niet de extra ruimte samenvoegen Sort gebruikt. We partitioneren de lijst rond een pivot-element, Sorteren waarden rond de pivot.

uitleg

snelle sortering begint met het partitioneren van de lijst – het kiezen van een waarde van de lijst die op zijn gesorteerde plaats zal staan. Deze waarde wordt een pivot genoemd., Alle elementen kleiner dan het draaipunt worden naar links verplaatst. Alle grotere elementen worden naar rechts verplaatst.

wetende dat de pivot zich op de juiste plaats bevindt, Sorteren we recursief de waarden rond de pivot totdat de hele lijst gesorteerd is.

Als u een gedetailleerd, speciaal artikel wilt lezen voor een snelle sortering, dan hebben we alles voor u!

implementatie

tijdscomplexiteit

het slechtste scenario is wanneer het kleinste of grootste element altijd als draaipunt wordt geselecteerd. Dit zou partities van grootte n-1 creëren, waardoor recursieve aanroepen n-1 keer worden veroorzaakt., Dit leidt ons tot een worst case tijd complexiteit van O(n^2).

hoewel dit een verschrikkelijk slecht geval is, wordt snel Sorteren veel gebruikt omdat de gemiddelde tijd complexiteit veel sneller is. Terwijl de functie partition geneste while loops gebruikt, doet het vergelijkingen op alle elementen van de array om de swaps te maken. Als zodanig heeft het een tijdscomplexiteit van O (n).

met een goede pivot zou de functie Snelle sortering de array in helften verdelen die logaritmisch met n groeit. daarom is de gemiddelde tijdscomplexiteit van het algoritme snelle sortering O (nlog (n)).,

Python ‘ s ingebouwde sorteerfuncties

hoewel het nuttig is om deze sorteeralgoritmen te begrijpen, zou u in de meeste Python-projecten waarschijnlijk de sorteerfuncties gebruiken die al in de taal beschikbaar zijn.,

We kunnen onze lijst om de inhoud ervan gesorteerd met de sort() methode:

apples_eaten_a_day = apples_eaten_a_day.sort()print(apples_eaten_a_day) # 

Of we kunnen gebruik maken van de sorted() functie voor het maken van een nieuwe gesorteerde lijst:

apples_eaten_a_day_2 = sorted_apples = sorted(apples_eaten_a_day_2)print(sorted_apples) # 

Ze beide in oplopende volgorde sorteren, maar u kunt gemakkelijk sorteren in aflopende volgorde door het instellen van de reverse vlag True:

in Tegenstelling tot de sorteer-algoritme functies die we hebben gemaakt, zowel deze functies kunt sorteren lijsten tupels en klassen., De sorted() functie kan elk iterabel object sorteren en dat omvat-lijsten, strings, tuples, woordenboeken, sets, en aangepaste iterators die u kunt maken.

Deze sorteerfuncties implementeren het Tim sortalgoritme, een algoritme geïnspireerd door Merge Sort en Insertion Sort.

Snelheidsvergelijkingen

om een idee te krijgen van hoe snel ze presteren, genereren we een lijst van 5000 nummers tussen 0 en 1000. We bekijken dan hoe lang het duurt voordat elk algoritme is voltooid. Dit wordt 10 keer herhaald, zodat we betrouwbaarder een prestatiepatroon kunnen vaststellen.,

Dit waren de resultaten, de tijd is in seconden:

u krijgt verschillende waarden als u de test zelf instelt, maar de waargenomen patronen moeten hetzelfde of vergelijkbaar zijn. Bubble Sort is de traagste de slechtste performer van alle algoritmen. Hoewel het nuttig is als een introductie tot sorteren en algoritmen, is het niet geschikt voor praktisch gebruik.

We merken ook dat Quick Sort erg snel is, bijna twee keer zo snel als Merge Sort en het zou niet zoveel ruimte nodig hebben om te draaien. Bedenk dat onze partitie was gebaseerd op het middelste element van de lijst, verschillende partities kunnen verschillende resultaten hebben.,

omdat invoegen veel minder vergelijkingen uitvoert dan selectie Sorteren, zijn de implementaties meestal sneller, maar in deze runs is Selectie Sorteren iets sneller.

Insertiesoorten doen veel meer swaps dan selectie Sorteren. Als het ruilen van waarden aanzienlijk meer tijd in beslag neemt dan het vergelijken van waarden, dan is dit “tegengestelde” resultaat plausibel.

Houd rekening met de omgeving bij het kiezen van uw sorteeralgoritme, omdat dit de prestaties beïnvloedt.

conclusie

sorteeralgoritmen geven ons vele manieren om onze gegevens te ordenen., We keken naar 6 verschillende algoritmen-Bubble Sort, selectie Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort-en hun implementaties in Python.

de hoeveelheid vergelijking en swaps die het algoritme uitvoert samen met de omgeving die de code uitvoert, zijn belangrijke determinanten van de prestaties. In echte Python-toepassingen, is het aanbevolen dat we vasthouden aan de ingebouwde Python sorteerfuncties voor hun flexibiliteit op de invoer en snelheid.