[Powered by Google Translate] TOMMY: Oglejmo si neke izbire, algoritem za sprejetje seznama številk in njihovo razvrščanje. Algoritem, se spomnite, je le korak-po-korak Postopek za dokončanje opravila. Osnovna ideja neke izbire je razdeliti naš seznam na dva dela - razporejene del in del razvrščeni. Na vsakem koraku algoritma je število preselil iz neprebrani del na izločen del, dokler sčasoma Celoten seznam je urejen. Torej, tukaj je seznam šestih številk - 23, 42, 4, 16, 8, in 15. Zdaj je celoten seznam šteje nesortirani. Čeprav se številka 16, kot je že bilo v njegovo pravilno mesto, naš algoritem ne more vedeti, da dokler Celoten seznam je urejen. Torej bomo upoštevali vsako številko, ki se nerazvrščeno dokler ne razvrstite ga sami. Vemo, da želimo, da seznam, ki bo v naraščajočem vrstnem redu. Torej bomo želeli zgraditi urejen del našega seznama od leve proti desni, najmanjšega do največjega. Da bi to dosegli, bomo morali najti najnižjo neurejen element in ga na koncu razvrščenih dela. Ker se ta seznam ni urejen, je edini način za to je, da poglej vsak element v nesortiranih dela, se spomnimo kateri element je najnižja in primerjavo Vsak element za to. Torej bomo prvi pogled na 23 let. To je prvi element, ki smo jih videli, zato smo se bom zapomnila to je minimum. Nato bomo pogledali 42. 42 je večje od 23, tako da je še vedno 23 najnižji. Nato je 4, ki je manj kot 23, tako da boste zapomnili 4 kot novi minimum. Naslednja je 16, ki je večja od 4, zato 4 je še vedno najnižja. 8 je večja od 4 in 15 je večje od 4, 4, tako mora biti najmanjši neprebrani element. Torej, čeprav so ljudje lahko takoj videli, da je 4 minimalni element, naš algoritem potrebuje, da pogled na Vsak element razvrščeni tudi po tem, ko smo ugotovili, 4 - je Najmanjša element. Torej, zdaj, ko smo ugotovili najmanjšo element, 4, bomo želeli premakniti v izločen del seznama. Ker je to prvi korak, to pomeni, da želimo postaviti na 4 začetek seznama. Zdaj 23 je na začetku seznama, tako da kaj je swap 4 in 23. Torej, zdaj je naš seznam izgleda takole. Vemo, da mora biti 4 na njegovo končno lokacijo, saj je tako je najmanjši element in element na začetku seznama. Torej to pomeni, da ne bomo kdaj morali premakniti še enkrat. Torej ponovite postopek dodati še en element za razporejene del seznama. Vemo, da nam ni treba gledati na 4, saj je že urejeno. Torej, lahko začnemo na 42, ki jih bomo spominjali, kot Najmanjša element. Torej, naslednjič bomo pogled na 23, kar je manj kot 42, tako da smo zapomni 23 je nova najnižja. Nato smo videli 16, ki je manj kot 23, tako da 16 je nova najnižja. Zdaj gledamo na 8, kar je manj kot 16, tako da 8 je nova najnižja. In na koncu 8 je manj kot 15, tako da vemo, da je minimalno 8 neprebrani element. Torej to pomeni, da je treba priložiti 8 do razporejene Del seznama. Zdaj 4 je edini element, razporejene, zato želimo, da se 8 ob 4. Ker 42 je prvi element v nesortiranih del Seznam bomo želeli, da bi zamenjali 42 in 8. Torej, zdaj je naš seznam izgleda takole. 4 in 8 predstavljajo urejen del seznama, in ostale številke predstavljajo unsorted Del seznama. Torej, kaj je še z drugo ponovitev. Začeli smo s 23 tokrat, saj nam ni treba gledati 4 in 8 več, ker oni ' že urejeno. 16 je manj kot 23, tako da boste zapomnili 16 kot novi minimum. 16 je manj kot 42, vendar 15 je manj kot 16, tako da mora biti 15 Najmanjša neprebrani element. Torej, zdaj smo želeli, da bi zamenjali 15 in 23 do nam ta seznam. Urejen del seznama je sestavljen iz 4, 8 in 15, ter Ti elementi so še vedno nesortirano. Vendar je prav tako se zgodi, da se naslednji neprebrani element, 16, je že urejeno. Vendar pa ni način za naš algoritem vedeti, da 16 je že v svojem pravem mestu, zato moramo še ponovite natanko isti postopek. Tako vidimo, da je 16 manj kot 42, in 16, je manj kot 23, tako da 16 mora biti najmanj element. Nemogoče je, da bi zamenjali ta element sam s sabo, tako da smo lahko preprosto pustite na tej lokaciji. Zato se moramo še eno podajo našega algoritma. 42 je več kot 23, tako da mora biti 23 Najmanjša neprebrani element. Ko bomo zamenjali 23 in 42, smo na koncu z naš končni razporejene seznam - 4, 8, 15, 16, 23, 42. Vemo 42 mora biti na pravem mestu, saj je Edini element levo, in da je izbira vrste. Pojdimo zdaj formalizirati svoj algoritem z nekaterimi psevdokod. Na liniji, lahko vidimo, da se moramo vključiti v vsak element seznama. Razen zadnjega elementa, saj je 1 element Seznam je že urejeno. Na liniji, menimo, da je prvi del nerazvrščenih del seznama, ki je minimalna, tako kot smo z našimi Na primer, da imamo kaj za primerjati. Linija 3 se prične drugo zanko, v kateri smo Ponovil več vsak neprebrani element. Vemo, da ko sem iteracij, razvrščenih del na našem seznamu, mora imeti i elementi v njih od vsakega koraka razvrsti enega elementa. Torej je treba prvi neprebrani element v položaju, jaz plus 1. Na liniji 4 primerjamo trenutni element na minimum Element, ki smo jih videli do sedaj. Če je trenutna element je manjša od minimalne element, potem ne pozabite trenutni element kot nova najmanj na liniji 5. Končno, na progah, 6 in 7, smo zamenjali vsaj element s prvim nesortiranih element, s čimer jo dodali v izločen del seznama. Ko imamo algoritem, pomembno vprašanje vprašati sebe kot programerjev je, kako dolgo je to trajalo? Mi bomo najprej vprašati vprašanje, kako dolgo traja, da za to algoritem za vožnjo v najslabšem primeru? Recall mi predstavlja to delovanje tokrat z velikim O zapisu. Za določitev najnižje neurejen element, smo v bistvu je za primerjavo vsak element v seznamu vsak drugi element v seznamu. Intuitivno, to zveni kot O kvadrat delovanje n. Če pogledamo na našem psevdokod, imamo tudi ugnezdena znotraj zanke drugega kroga, ki dejansko zveni kot O za kvadratni delovanje n. Vendar ne pozabite, da nam ni treba pogledati čez Celoten seznam pri določanju minimalnega neurejen element? Ko bomo vedeli, da je bil razvrščen 4, na primer, nismo treba pogledati še enkrat. Torej, ali to nižje teče čas? Za naš seznam dolžine 6, smo morali narediti 5 primerjave za prvi element, štiri primerjave za Drugi element, in tako naprej. To pomeni, da je skupno število korakov je vsota Množica celih števil od 1 do dolžine seznama minus 1. Mi lahko predstavlja to s seštevanjem. Mi ne bo šel v summations tukaj. Vendar se je izkazalo, da je ta vsota enaka n-krat n minus 1 več kot 2. Ali enakovredno n kvadrat več kot 2 minus n čez 2. Ko govorimo o asimptotične runtime, to n kvadrat izraz bo prevladovala ta izraz n. Torej, izbira je nekako O izmed n kvadrat. Spomnimo, da je v našem primeru, izbor sort še vedno potrebna preveri, če je število, ki je bil že razporejene potrebno premakniti. To pomeni, da če bi tekel izbiro vrste kot je že razporejene seznam, bi bilo potrebno enako število korakov, kot je bi med vožnjo na popolnoma nesortiranih seznama. Torej, izbira sort je najboljši primer uspešnost n kvadrat, ki jih predstavljajo z omega n kvadrat. In to je to za neke izbire. Samo eden od mnogih algoritmov smo lahko uporabite za razvrščanje seznama. Moje ime je Tommy, in to je cs50.