[Přehrávání hudby] DOUG LLOYD: Selection sort je algoritmus, který, jak se dalo očekávat, třídí soubor prvků. A algoritmus odvolání je krok-za-krokem set instrukcí pro dokončení úkolu. 

Při výběru setřiďte Základní myšlenka je to, najít nejmenší netříděného prvek a přidat do konce tříděného seznamu. Účinně, co to dělá, je build seřazeným seznam, jeden prvek najednou. Rozebrat to k pseudokódu jsme mohli konstatovat tento algoritmus takto, opakujte, dokud žádné netříděné prvky zůstávají. Prostřednictvím netříděného vyhledávání Údaje najít nejmenší hodnotu, pak vymění nejmenší hodnotu s První prvek netříděného části. 

To může pomoci vizualizovat to, takže se pojďme podívat na to. Takže to, tvrdím, je netříděný pole a já jsem indikováno to tím, že všechny uvedením prvky jsou v červené barvě, nejsou dosud seřazeny. Toto je úplná netříděný součástí pole. 

Takže pojďme projít kroky výběr třídit třídit tohoto pole. Takže znovu, budeme opakovat do žádné netříděné prvky zůstávají. Budeme prohledávat Údaje najít nejmenší hodnotu, a pak se vymění tuto hodnotu s První prvek netříděného části. 

Právě teď, znovu, celý pole je netříděného část. Všechny červenými prvky jsou netříděný. Tak jsme prohledávat a najdeme nejmenší hodnotu. Začneme na začátku, jdeme až do konce, najdeme nejmenší hodnota je jedna. Takže to je první část. A pak druhá část, vyměnit tuto hodnotu první prvek netříděného části, nebo první červený prvek. 

V tomto případě, že by bylo pět, takže jsme se vyměnit jedno a pět. Když to uděláme, můžeme vizuálně vidět, že máme pohyboval nejmenší hodnotě prvku matice, na samém počátku. Účinně třídění tento prvek. 

A tak můžeme skutečně potvrdit, a uvádí, že jeden, je třídit. A tak budeme uvádět seřazené část našeho pole, zbarvením to modré. 

Teď už jen opakovat postup. Hledáme přes netříděného část pole najít nejmenší prvek. V tomto případě je to dva. 

Jsme vyměnit, že s prvním prvek netříděného části. V tomto případě dvou je shodou okolností také první prvek netříděného části. Tak jsme vyměnit dva se sebou samým, která opravdu jen dva listy tam, kde je, a to seřazeny. Pokračování na, jsme prohledávat najít nejmenší prvek. Je to tři. Jsme vyměnit ji s prvním prvek, který je pět. A teď tři je seřazen. 

Hledáme ještě jednou, a my najít nejmenší prvek je čtyři. My ji vyměnit s prvním prvkem z netříděný část, a teď čtyřmi je tříděn. 

Zjistili jsme, že pět je nejmenší prvek. Jsme vyměnit ji s prvním prvek netříděného části. A teď se pět seřazeny. 

A pak konečně, naše netříděný část tvoří pouhého jednoho prvku, tak jsme prohledávat a zjistíme, že šest je nejmenší, a ve skutečnosti, jediným prvkem. A pak můžeme konstatovat, že je tříděn. A teď jsme zapnutý naší nabídku od bytí úplně nevytříděné v červené barvě, zcela seřazena v modré, s použitím výběrem Třídit. 

Takže to, co je tady ten nejhorší možný scénář? No v absolutně nejhorší případ, musíme se dívat přes všechny prvky pole na najít nejmenší netříděného prvek, a musíme zopakovat tento proces n-krát. Jednou pro každý prvek matice protože jen my, v tomto algoritmu, třídit jeden prvek v čase. 

Jaký je nejlepší scénář? No to je přesně to samé, že jo? Vlastně jsme muset stále procházet každý prvek pole aby bylo možné potvrdit, že to je, ve skutečnosti, že nejmenší prvek. 

Takže nejhorší případ runtime, my muset opakovat proces n-krát, jednou pro každý z n elementy. A v nejlepším případě, musíme udělat totéž. 

Tak vzpomínal na náš výpočetní složitost toolbox, co si myslíte, že je to nejhorší pouzdro runtime pro výběr druhu? Co si myslíte, že je nejlepší pouzdro runtime pro výběr druhu? 

Věděli jste asi velký O z n na druhou, a Big Omega n na druhou? Vy byste mít pravdu. To jsou, ve skutečnosti, nejhorší případ a nejlepší případ běh časy, pro výběr druhu. 

Jsem Doug Lloyd. To je CS50.