Tip:
Highlight text to annotate it
X
>> [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.