[Speel van musiek] DOUG LLOYD: Seleksie soort is 'n algoritme wat, soos jy kan verwag, sorteer 'n stel van elemente. En algoritme herroep is 'n stel stap-vir-stap instruksies vir die voltooiing van 'n taak. 

In seleksie sorteer die basiese idee is dit, vind die kleinste ongesorteerde element en voeg dit by die einde van die gesorteerde lys. Effektief wat dit doen, is die bou 'n gesorteerde lys, een element op 'n slag. Breek dit af na pseudokode ons kon hierdie algoritme meld soos volg, herhaal totdat geen ongesorteerde elemente bly. Soek deur die ongesorteerde data na die kleinste waarde vind, dan ruil die kleinste waarde van die eerste element van die ongesorteerde deel. 

Dit kan help om hierdie visualiseer, so laat ons neem 'n blik op hierdie. So hierdie, ek stry, is 'n ongesorteerde verskeidenheid en ek het aangedui dat hy deur aan te dui dat alle van die elemente is rooi gekleur, hulle nog nie gesorteer. Dit is die hele ongesorteerde deel van die skikking. 

So laat ons gaan deur die stappe van seleksie soort om hierdie verskeidenheid te sorteer. So weer, ons gaan herhaal totdat daar geen ongesorteerde elemente bly. Ons gaan soek deur die data na die kleinste waarde vind, en dan ruil wat waarde by die eerste element van die ongesorteerde deel. 

Nou, weer, die hele skikking is die ongesorteerde deel. Al die elemente is rooi ongesorteerde. So soek ons ​​deur en vind ons die kleinste waarde. Ons begin by die begin, ons gaan na die einde, vind ons die kleinste waarde is, een. So dit is deel een. En dan deel twee, ruil wat waarde met die eerste element van die ongesorteerde deel, of die eerste rooi element. 

In hierdie geval sal dit nie wees vyf, so ons ruil een en vyf. Wanneer ons dit doen, kan ons visueel sien dat ons het verskuif die kleinste waarde element van die skikking, na die begin. Effektief te sorteer daardie element. 

En so kan ons inderdaad bevestig en staat wat een word gesorteer. En so sal ons die gedeelte dui gesorteer van ons skikking, deur kleur dit blou. 

Nou het ons net weer herhaal die proses. Ons soek deur die ongesorteerde deel van die skikking na die kleinste element te vind. In hierdie geval, dit is twee. 

Ons ruil dat met die eerste element van die ongesorteerde deel. In hierdie geval twee gebeur ook te wees die eerste element van die ongesorteerde deel. So ruil ons twee met homself, wat eintlik net laat twee waar dit is, en dit is gesorteer. Voortgesette op, soek ons ​​deur die kleinste element te vind. Dit is drie. Ons ruil dit met die eerste element, wat vyf. En nou drie gesorteer. 

Ons soek weer deur, en ons vind die kleinste element is vier. Ons ruil dit met die eerste element van die ongesorteerde deel, en nou vier gesorteer. 

Ons vind dat vyf is die kleinste element. Ons ruil dit met die eerste element van die ongesorteerde deel. En nou vyf gesorteer. 

En dan laastens, ons ongesorteerde gedeelte bestaan van net 'n enkele element, sodat ons soek deur en ons vind dat ses is die kleinste, en in werklikheid, net element. En dan kan ons sê dat dit gesorteer. En nou het ons ons verskeidenheid aangeskakel uit om heeltemal Unsorted in rooi, heeltemal gesorteer in blou, met behulp van seleksie soort. 

So, wat is die ergste geval scenario hier? Wel, in die absolute ergste geval, ons het om te kyk oor al die elemente van die skikking te vind die kleinste ongesorteerde element, en ons moet herhaal hierdie proses n keer. Een keer vir elke element van die skikking want net wat ons in hierdie algoritme sorteer een element op die tyd. 

Wat is die beste scenario? Wel dit is presies dieselfde, reg? Ons het eintlik nog stap vir stap deur elke enkele element van die skikking om te bevestig dat dit is, in werklikheid, die kleinste element. 

So het die ergste geval runtime, ons moet 'n proses n keer herhaal, eens en vir elkeen van n elemente. En in die beste geval, ons het om dieselfde te doen. 

So dink terug aan ons rekenkundige kompleksiteit toolbox, wat dink jy is die ergste geval runtime vir keuring soort? Wat dink jy is die beste geval runtime vir keuring soort? 

Het jy raai Big O van n vierkant, en Big Omega van N kwadraat? Jy wil reg wees. Dit is, in werklikheid, die ergste geval en die beste geval run tye, vir keuring soort. 

Ek is Doug Lloyd. Dit is CS50.