[Muziek] DOUG LLOYD: Selection sort is een algoritme dat, zoals je zou verwachten, sorteert een set van elementen. En algoritme recall is een set van stap-voor-stap instructies voor het uitvoeren van een taak. 

In de selectie sorteren basisidee is dit, vindt de kleinste ongesorteerd element en toevoegen aan het einde van de gesorteerde lijst. Effectief wat dit doet is build een gesorteerde lijst, één element tegelijk. Het af te breken om pseudocode we dit algoritme vermelden als volgt, herhaal dit tot geen ongesorteerde elementen blijven. Doorzoek de ongesorteerde gegevens aan de kleinste waarde te vinden, dan wisselen de kleinste waarde met de eerste element van het ongesorteerde deel. 

Het kan helpen om dit te visualiseren, dus laten we eens een kijkje op deze. Dus dit, ik beweer, is een ongesorteerde array en ik heb aangegeven dat zij door aan te geven dat alle van de elementen zijn rood gekleurd, ze zijn nog niet opgelost. Dit is de gehele ongesorteerde deel van de array. 

Dus laten we gaan door de stappen van selectie sorteren op deze array te sorteren. Dus nogmaals, we gaan herhalen tot er geen ongesorteerde elementen blijven. We gaan zoeken via de gegevens aan de kleinste waarde te vinden, en wisselen die waarde met eerste element van het ongesorteerde deel. 

Nu, nogmaals, de hele array is de ongesorteerde deel. Alle rode elementen zijn ongesorteerd. Dus zoeken we door en vinden we de kleinste waarde. We beginnen bij het begin, gaan we naar het einde, vinden we de kleinste waarde één. Dus dat is deel één. En dan deel twee, wisselen die waarde met het eerste element van het ongesorteerde deel, of de eerste rode element. 

In dit geval zou dat vijf, dus we ruilen een en vijf. Als we dat doen, kunnen we visueel te zien dat we hebben bewoog de kleinste gewaardeerd element van de matrix, aan het begin. Effectief sorteren van dat element. 

En zo kunnen we wel bevestigen en verklaren dat men, wordt gesorteerd. En dus zullen we de gesorteerde gedeelte geven van ons aanbod, door te kleuren blauw. 

Nu zijn we gewoon opnieuw herhaal het proces. We zoeken in de ongesorteerde deel van de array om het kleinste element te vinden. In dit geval, het is twee. 

We wisselen die met de eerste element van het ongesorteerde deel. In dit geval twee toevallig ook het eerste element van het ongesorteerde deel. Zo wisselen we twee met zichzelf, die eigenlijk alleen maar laat twee waar het is, en het is opgelost. Voortbordurend op, zoeken we door het kleinste element te vinden. Het is drie. We ruilen met het eerste element, dat vijf. En nu drie wordt gesorteerd. 

We doorzoeken opnieuw, en we vind het kleinste element is vier. We ruilen met het eerste element van de ongesorteerd deel, en nu vier wordt gesorteerd. 

We vinden dat de vijf is het kleinste element. We ruilen met het eerste element van het ongesorteerde deel. En nu vijf wordt gesorteerd. 

En dan tot slot, onze ongesorteerde deel bestaat van slechts één element, dus we zoeken door middel van en wij vinden dat zes is de kleinst, en in feite slechts element. En dan kunnen we stellen dat het wordt gesorteerd. En nu hebben we ons aanbod overgestapt volledig wordt ongesorteerd rood, volledig gesorteerd in blauw, met selectie sorteren. 

Dus wat is het worst case scenario hier? Welnu, in de absolute slechtste geval is, moeten we kijken over alle elementen van de array vindt de kleinste ongesorteerd element, en we moeten herhalen Dit proces n keer. Eenmaal voor elk element van de array want alleen wij in dit algoritme sort één element op het moment. 

Wat is de beste case scenario? Nou het is precies hetzelfde, toch? We hebben eigenlijk nog te doorlopen elk element van de array om te bevestigen dat het, in feite het kleinste element. 

Dus het ergste geval runtime, we moet een proces n keer herhalen, eenmaal voor elk van de n elementen. En in het beste geval, we hebben om hetzelfde te doen. 

Dus denken terug naar onze computationele complexiteit toolbox, wat denk je dat is het ergste Bij runtime voor de selectie sorteren? Wat denk je dat is de beste Bij runtime voor de selectie sorteren? 

Hebt u raden Big O n kwadraat, en Big Omega n kwadraat? Je zou gelijk hebben. Dit zijn in feite de worst case en best case run tijden, voor de selectie sorteren. 

Ik ben Doug Lloyd. Dit is CS50.