[Prehrávanie hudby] DOUG LLOYD: Selection sort je algoritmus, ktorý, ako sa dalo očakávať, triedi súbor prvkov. A algoritmus odvolanie je krok-za-krokom set inštrukcií pre dokončenie úlohy. 

Pri výbere Roztieďte Základná myšlienka je to, nájsť najmenší netriedeného prvok a pridať do konca triedeného zoznamu. Účinne, čo to robí, je build zoradeným zoznam, jeden prvok naraz. Rozobrať to k pseudokódu sme mohli konštatovať tento algoritmus takto, opakujte, kým žiadne netriedené prvky zostávajú. Prostredníctvom netriedeného vyhľadávanie Údaje nájsť najmenšiu hodnotu, potom vymení najmenšiu hodnotu s Prvý prvok netriedeného časti. 

To môže pomôcť vizualizovať to, takže sa poďme pozrieť na to. Takže to, tvrdím, je netriedený poľa a ja som indikované to tým, že všetky uvedením prvky sú v červenej farbe, nie sú dosiaľ zoradené. Toto je úplná netriedený súčasťou poľa. 

Takže poďme prejsť krokmi výber triediť triediť tohto poľa. Takže znova, budeme opakovať do žiadnej netriedené prvky zostávajú. Budeme prehľadávať Údaje nájsť najmenšiu hodnotu, a potom sa vymení túto hodnotu s Prvý prvok netriedeného časti. 

Práve teraz, znovu, celý pole je netriedeného časť. Všetky červenými prvkami sú netriedený. Tak sme prehľadávať a nájdeme najmenšiu hodnotu. Začneme na začiatku, ideme až do konca, nájdeme najmenšia hodnota je jedna. Takže to je prvá časť. A potom druhá časť, vymeniť túto hodnotu prvý prvok netriedeného časti, alebo prvý červený prvok. 

V tomto prípade, že by bolo päť, takže sme sa vymeniť jedno a päť. Keď to urobíme, môžeme vizuálne vidieť, že máme pohyboval najmenšie hodnote prvku matice, na samom počiatku. Účinne triedenie tento prvok. 

A tak môžeme skutočne potvrdiť, a uvádza, že jeden, je triediť. A tak budeme uvádzať zoradené časť nášho poľa, sfarbením to modré. 

Teraz už len opakovať postup. Hľadáme cez netriedeného časť pole nájsť najmenší prvok. V tomto prípade je to dva. 

Sme vymeniť, že s prvým prvok netriedeného časti. V tomto prípade dvoch je zhodou okolností tiež prvý prvok netriedeného časti. Tak sme vymeniť dva so sebou samým, ktorá naozaj len dva listy tam, kde je, a to zoradené. Pokračovanie na, sme prehľadávať nájsť najmenší prvok. Je to tri. Sme vymeniť ju s prvým prvok, ktorý je päť. A teraz tri je zoradený. 

Hľadáme ešte raz, a my nájsť najmenší prvok je štyri. My ju vymeniť s prvým prvkom z netriedený časť, a teraz štyrmi je triedený. 

Zistili sme, že päť je najmenší prvok. Sme vymeniť ju s prvým prvok netriedeného časti. A teraz sa päť zoradené. 

A potom konečne, naša netriedený časť tvorí púheho jedného prvku, tak sme prehľadávať a zistíme, že šesť je najmenšie, a v skutočnosti, jediným prvkom. A potom môžeme konštatovať, že je triedený. A teraz sme zapnutý našu ponuku od bytia úplne nevytriedené v červenej farbe, úplne zoradená v modrej, s použitím výberom Triediť. 

Takže to, čo je tu ten najhorší možný scenár? No v absolútne najhoršie prípad, musíme sa pozerať cez všetky prvky poľa na nájsť najmenší netriedeného prvok, a musíme zopakovať tento proces n-krát. Raz pre každý prvok matice pretože len my, v tomto algoritmu, triediť jeden prvok v čase. 

Aký je najlepší scenár? No to je presne to isté, že jo? Vlastne sme musieť stále prechádzať každý prvok poľa aby bolo možné potvrdiť, že to je, v skutočnosti, že najmenší prvok. 

Takže najhorší prípad runtime, my musieť opakovať proces n-krát, raz pre každý z n elementy. A v najlepšom prípade, musíme urobiť to isté. 

Tak spomínal na náš výpočtovej zložitosť toolbox, čo si myslíte, že je to najhoršie puzdro runtime pre výber druhu? Čo si myslíte, že je najlepší puzdro runtime pre výber druhu? 

Vedeli ste asi veľký O z n na druhú, a Big Omega n na druhú? Vy by ste mať pravdu. To sú, v skutočnosti, najhorší prípad a najlepší prípad beh časy, pre výber druhu. 

Som Doug Lloyd. To je CS50.