>> [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.