>> [Muusika mängib]
DOUG LLOYD: Valik omamoodi on algoritmi, et te võite arvata,
sorteerib elementidega.
Ja algoritm tagasikutsumine on samm-sammult komplekt
käskude täitmise ülesanne.
>> Veinide sorteerida Põhiidee on see,
Leida väikseim sorteerimata element ja lisada see lõpuks sorteeritud nimekirja.
Tõhusalt Mis see on ehitada Sorteeritud nimekirja, üks element korraga.
Breaking see alla pseudokoodi me võiks väita seda algoritmi
järgmiselt korda seda kuni no sorteerimata elemendid jäävad.
Otsige sorteerimata andmete leida väikseim väärtus,
siis vahetada väiksema väärtusega koos Esimene osa sorteerimata osa.
>> See võib aidata visualiseerida seda, Võtame pilk see.
Nii et see, ma väita, on sorteerimata massiivi ja ma olen
märkinud, näidates, et kõik elemendid on punased,
need pole veel sorteerida.
See on kogu sorteerimata osa massiivi.
>> Nii lähme läbi sammud valikut omamoodi sorteerida seda valikut.
Nii jälle, me saame korrata kuni ei sorteerimata elemendid jäävad.
Me teeme otsida andmete leida väikseim väärtus,
ja siis vahetada, et väärtus koos Esimene osa sorteerimata osa.
>> Praegu jälle kogu massiiv on sorteerimata osa.
Kõik punase elemendid sorteerimata.
Nii me otsida ja leiame väikseim väärtus.
Me alustame algusest, läheme lõpuni,
leiame väikseim väärtus on üks.
Nii et esimene osa.
Ja siis teine ​​osa, vahetada, et väärtus esimene osa sorteerimata osa,
või esimese punase element.
>> Sellisel juhul oleks viis, nii et me vahetada üks kuni viis.
Kui me seda teeme, saame visuaalselt näha, et me oleme
kolis väikseim väärtus element massiivi, et algusest peale.
Tõhusalt sorteerimine, et element.
>> Ja nii me saame tõepoolest kinnitada ja väidavad, et üks on järjestatud.
Ja nii me näitavad järjestatud osa meie massiivi, värvimine see sinine.
>> Nüüd jääb üle vaid korrata protsessi uuesti.
Me otsida sorteerimata osa massiivi leida väikseim element.
Sel juhul on kaks.
>> Me vahetada, et esimese element sorteerimata osa.
Sel juhul kaks ka juhtub olema esimene osa sorteerimata osa.
Nii me swap kaks iseendaga mis tõesti lihtsalt jätab kaks
kus see on, ja see on järjestatud.
Jätkub me otsida leida kõige väikseim element.
See on kolm.
Me vahetada see esimene element, mis on viis.
Ja nüüd kolm on järjestatud.
>> Me otsida uuesti, ja me Leida väikseim element on neli.
Me vahetada see esimene osa sorteerimata osa, ja nüüd neli on järjestatud.
>> Me leiame, et viis on väikseim element.
Me vahetada see esimene element sorteerimata osa.
Ja nüüd viis on järjestatud.
>> Ja siis lõpuks, meie sorteerimata osa koosneb
vaid ühe elemendi, nii et me otsida
ja me leiame, et kuus on väikseim, ja tegelikult ainus element.
Ja siis saame väita, et see on järjestatud.
Ja nüüd me oleme lülitatakse meie massiivi alates on täiesti Sorteerimata
punane, täielikult järjestatud sinine, kasutades valikut omamoodi.
>> Mis siis halvimal juhul siin?
Noh absoluutne halvim Juhul, me peame vaatama üle
kõik elemendid massiivi Leida väikseim sorteerimata element,
ja me peame kordama Selle protsessi n korda.
Kui iga element massiivi sest me ainult selle algoritmi,
Sorteeri üks element ajal.
>> Milline on parim stsenaarium?
Aga see on täpselt sama, eks ole?
Me tegelikult on ikka sammult läbi iga element massiivi
et kinnitada, et see on, tegelikult väikseim element.
>> Nii et halvimal juhul runtime, me kordama protsessi n korda,
üks kord iga n elemente.
Ja parimal juhul, me peame tegema sama.
>> Nii mõeldes meie arvutuslik keerukus tööriistakasti,
Mis sa arvad, on kõige hullem Juhul runtime valiku omamoodi?
Mis te arvate, on parim Juhul runtime valiku omamoodi?
>> Kas sa vist Big O n ruudus ja Big Omega n ruudus?
Sa oleks õige.
Need on, et tegelikult Halvimal juhul ja parimal juhul run
korda, valiku omamoodi.
>> Ma olen Doug Lloyd.
See on CS50.