Een tour van de top-5 van sorteer-algoritme met Python code


Sorteer-algoritme complexiteit’

Sorteren is een vaardigheid die elke software ingenieur en ontwikkelaar moet weten. Niet alleen om codering interviews door te geven, maar als een algemeen begrip van de programmering zelf., De verschillende sorteeralgoritmen zijn een perfecte showcase van hoe algoritmeontwerp zo ‘ n sterk effect kan hebben op de complexiteit, snelheid en efficiëntie van het programma.

laten we een rondleiding nemen door de top 6 sorteeralgoritmen en zien hoe we ze kunnen implementeren in Python!

Bubble sort is degene die gewoonlijk wordt onderwezen in inleidende CS klassen omdat het duidelijk laat zien hoe Sorteren werkt terwijl het eenvoudig en gemakkelijk te begrijpen is. Bubble Sorteren stappen door de lijst en vergelijkt aangrenzende paren van elementen. De elementen worden verwisseld als ze in de verkeerde volgorde staan., De doorloop door het ongesorteerde gedeelte van de lijst wordt herhaald totdat de lijst is gesorteerd. Omdat Bubble sort herhaaldelijk door het ongesorteerde deel van de lijst gaat, heeft het een worst case complexiteit van O(n2).

Selectie Sorteren

Selectie sorteren is ook vrij eenvoudig, maar vaak beter presteert dan de bubble sort., Als u kiest tussen de twee, is het het beste om gewoon standaard recht op Selectie Sorteren. Met selectie Sorteren verdelen we onze invoerlijst / array in twee delen: de sublist van items die al gesorteerd zijn en de sublist van items die nog gesorteerd moeten worden die de rest van de lijst vormen. We vinden eerst het kleinste element in de ongesorteerde sublist en plaatsen het aan het einde van de gesorteerde sublist. Zo grijpen we continu het kleinste ongesorteerde element en plaatsen het in gesorteerde volgorde in de gesorteerde sublist. Dit proces gaat iteratief door totdat de lijst volledig gesorteerd is.,

Insertion Sort

Insertion sort sneller is en ook-misschien wel eenvoudiger dan zowel bubble sort en selectie sorteren. Grappig genoeg, het is hoeveel mensen Sorteren hun kaarten bij het spelen van een kaartspel! Bij elke lus-iteratie verwijdert insertion sort één element uit de array., Het vindt dan de locatie waar dat element hoort binnen een andere gesorteerde array en voegt het daar in. Het herhaalt dit proces totdat er geen invoerelementen overblijven.

Merge Sort

Merge sort is een perfect elegant voorbeeld van een Verdeel en Heers algoritme., Het eenvoudig maakt gebruik van de 2 belangrijkste stappen van een dergelijk algoritme:

(1) deel continu de ongesorteerde lijst totdat je N sublists hebt, waarbij elke sublist 1 element heeft dat “ongesorteerd” is en N het aantal elementen in de originele array is.

(2) herhaaldelijk samenvoegen dat wil zeggen de sublists 2 tegelijk samenvoegen om nieuwe gesorteerde sublists te produceren totdat alle elementen volledig zijn samengevoegd in een enkele gesorteerde array.,

Quick Sort

Snel sorteren is ook een verdeel en heers algoritme zoals merge sort. Hoewel het een beetje ingewikkelder, in de meeste standaard implementaties presteert het aanzienlijk sneller dan merge sort en zelden bereikt de slechtste geval complexiteit van O (n2)., Het heeft 3 hoofdstappen:

(1) We selecteren eerst een element dat we het pivot uit de array zullen noemen.

(2) Verplaats alle elementen die kleiner zijn dan het draaipunt naar links van het draaipunt; Verplaats alle elementen die groter zijn dan het draaipunt naar rechts van het draaipunt. Dit wordt de partitiebewerking genoemd.

(3) recursief de bovenstaande 2 stappen afzonderlijk toepassen op elk van de sub-arrays van elementen met kleinere en grotere waarden dan de laatste pivot.,

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *