[Glazbom] Doug LLOYD: Izbor vrsta je algoritam koji, kao što bi ste očekivali, sortira niz elemenata. I algoritam opoziv je korak-po-korak set uputa za dovršetak zadatka. 

U izboru sortiranje Osnovna ideja je ovo, Pronađi najmanji nesortiranog element i dodati na kraju sortiranog popisa. Učinkovito što to čini se graditi popis razvrstani, jedan element u isto vrijeme. Razbijanje dolje pseudokod možemo navesti ovaj algoritam kako slijedi, ponovite sve dok nema Nesortirani elementi ostaju. Pretraži kroz nesortiran Podaci pronaći najmanju vrijednost, zatim zamijeniti najmanju vrijednost s Prvi element nerazvrstanog dijela. 

To može pomoći vizualizirati to, pa neka je pogledati ovo. Dakle, ovo, smatram, je nesortirani niz i imam to ukazuje ukazuje da je sve elemenata su crvene boje, oni još nisu razvrstani. Ovo je cijeli nesortirani dio polja. 

Tako ćemo proći kroz korake Izbor vrsta za sortiranje ovaj niz. Pa opet, mi ćemo ponoviti dok nema Nesortirani elementi ostaju. Ćemo potragu kroz Podaci pronaći najmanju vrijednost, a zatim zamijeniti tu vrijednost s Prvi element nerazvrstanog dijela. 

Upravo sada, opet, čitav Niz je Nesortirano dio. Sve od crvenih elemenata Nesortirano. Tako smo i pretraživanje nađemo najmanji vrijednost. Krećemo na početku, idemo do kraja, nađemo najmanji vrijednost, jedan. Dakle, to je jedan dio. A onda je dio dva, mijenjati tu vrijednost s Prvi element nerazvrstanog dijela, ili prvi crveni elementa. 

U tom slučaju bi se pet, tako da smo zamijeniti jedan i pet. Kada smo to učinili, možemo vizualno vidjeti da smo preselio najmanji vrijednosti elementa od polja, na samom početku. Učinkovito sortiranje taj element. 

I tako smo doista može potvrditi i tvrde da jedan, sortira. I tako ćemo navesti sortiran dio naše ponude, bojanje plava. 

Sada mi samo ponoviti postupak opet. Mi tražimo kroz nerazvrstani dio Niz pronaći najmanji element. U ovom slučaju, to dvoje. 

Mi mijenjati da s prvim element nerazvrstani dio. U ovom slučaju dva također dogoditi da se Prvi element nerazvrstanog dijela. Tako smo zamijeniti dva sa sebe, koji zapravo samo ostavlja dva gdje je, i to je riješeno. Nastavljajući se na, mi pretraživanje pronaći najmanji element. To je tri. Mi ga zamijeniti s prvim element, koji je pet. A sada tri je riješeno. 

Mi pretraživanje opet, i mi naći najmanji element je četiri. Mi ga zamijeniti s prvim elementom nesortirani dio, a sada četiri sortira. 

Smatramo da je pet najmanji element. Mi ga zamijeniti s prvim element nerazvrstani dio. A sada pet je riješeno. 

I onda na kraju, naš nesortiran dio sastoji od samo jednog elementa, pa smo pretraživanje a mi da šest je najmanji, i zapravo, jedini element. A onda možemo reći da je to riješeno. I sada smo prebacili našu niz od toga da bude potpuno nerazvrstani crveno, potpuno razvrstani u plavom, pomoću odabira vrste. 

Dakle, što je najgori mogući scenarij ovdje? Pa u apsolutno najgore slučaju, moramo gledati preko svi elemenata polja za Pronađi najmanji nesortiranog elementa, i moramo ponoviti ovaj proces N puta. Jednom za svaki element polja jer smo samo, u ovom algoritmu, sortirati jedan element na vrijeme. 

Koji je najbolji mogući scenarij? Pa to je točno isto, zar ne? Mi zapravo moramo još korak kroz svaki element polja kako bi potvrdili da je, u stvari, najmanji element. 

Dakle, u najgorem slučaju izvođenja smo morati ponoviti postupak n puta, jednom za svaki od n elemenata. I u najboljem slučaju, moramo učiniti isto. 

Dakle, razmišljam natrag u naš računalna složenost alatni, Što mislite je najgore Slučaj runtime za izbor vrste? Što mislite je najbolja Slučaj runtime za izbor vrste? 

Jeste li pogoditi Big O n na kvadrat, i Big Omega n na kvadrat? Ti bi biti u pravu. Oni su, u stvari, najgorem slučaju i najboljem slucaju pokrenuti puta, za odabir vrste. 

Ja sam Doug Lloyd. Ovo je CS50.