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