[Powered by Google Translate] TOMMY: Võtame pilk valik omamoodi, algoritm
võtmise numbrite loendi ja sorteerimine neid.
Algoritm, pea meeles, on lihtsalt samm-sammult
korra saavutamise ülesanne.
Põhiidee valik omamoodi on jagada
meie nimekirjas kaheks osaks -
järjestatud osa ja sorteerimata osa.
Igal sammul algoritm, number on liikunud
sortimata osal järjestatud osa kuni lõpuks
Kogu nimekiri on järjestatud.
Nii et siin on nimekiri kuus numbrit -
23, 42, 4, 16, 8, ja 15.
Just nüüd kogu nimekirja peetakse sortimata.
Kuigi arv nagu 16 võib olla juba oma õige
asukoht, meie algoritm on kuidagi võimalik teada, et kuni
Kogu nimekiri on järjestatud.
Nii et me käsitleme igat numbrit võib sortimata kuni me järjestada
seda ise.
Me teame, et me tahame nimekiri olema tõusvas järjestuses.
Nii et me tahame üles ehitada järjestatud osa meie nimekirja
vasakult paremale, väiksemast ja lõpetades suuremaga.
Selleks, et me peame leidma minimaalse sortimata element
ja pane see lõpus järjestatud osa.
Kuna see loetelu ei ole sorteeritud, ainus viis seda teha on
pilk iga element sorteerimata osa, meenutades
mis element on madalaim ja võrrelda
iga osa sellest.
Nii et me kõigepealt vaadata 23.
See on esimene element oleme näinud, nii me meeles
see minimaalseks.
Järgmine me vaatame 42.
42 on suurem kui 23, nii 23 on ikka vähe.
Järgmine on 4, mis on väiksem kui 23, nii me mäletama 4
kui uus minimaalselt.
Järgmine on 16, mis on suurem kui 4, seega 4
on veel minimaalne.
8 on suurem kui 4 ja 15 on suurem kui 4, SO 4 peavad olema
väikseim sortimata element.
Nii et kuigi inimestena saame kohe näha, et 4 on
minimaalne element, meie algoritm peab uurima
iga sortimata element, isegi kui me oleme leidnud 4 -
minimaalne element.
Nüüd, et oleme leidnud minimaalne element, 4, me tahame
liikuda see sorteeritakse osa nimekirjast.
Kuna see on esimene samm, see tähendab, et me taha panna 4 asendisse
loetelu alguses.
Praegu 23 on alguses nimekirja, nii
olgem vahetada 4 ja 23.
Nüüd meie nimekiri näeb välja selline.
Me teame, et 4 peab olema oma lõplik asukoht, sest see on
nii väikseim element ja element alguses
nimekirja.
Nii et see tähendab, et me ei ole kunagi vaja minna uuesti.
Nii et olgem korrake seda protsessi lisada veel üks element, mis
järjestatud osa nimekirjast.
Me teame, et meil ei ole vaja vaadata 4, sest see on
juba järjestatud.
Nii saame alustada kell 42, mis me mäletama kui
minimaalne element.
Nii et järgmine me vaatame 23, mis on vähem kui 42, nii et me
Jäta 23 on uus miinimum.
Järgmine näeme 16, mis on vähem kui 23, nii
16 on uus miinimum.
Nüüd vaatame 8, mis on väiksem kui 16, nii
8 on uus miinimum.
Ja lõpuks 8 on alla 15, nii et me teame, et 8 on minimaalne
sortimata element.
Nii et see tähendab, et peaksime lisama 8 järjestatud
osa nimekirjast.
Praegu 4 on ainult järjestatud element, nii et me tahame panna
8 kõrval 4.
Kuna 42 on esimene element sorteerimata osa
loetelu, me tahame, et vahetada 42 ja 8.
Nüüd meie nimekiri näeb välja selline.
4 ja 8 moodustavad järjestatud osa nimekirja ja
Ülejäänud numbrid näitavad sortimata
osa nimekirjast.
Nii et olgem jätkata teise iteratsiooni.
Alustame 23 seekord, sest me ei pea vaatama
4 ja 8 enam, sest need oleme
juba järjestatud.
16 on alla 23, nii me meeles
16 Nagu uus miinimum.
16 on väiksem kui 42, kuid 15 on alla 16, seega 15 peab olema
miinimum sortimata element.
Nii et nüüd me tahame vahetada 15 ja 23
anna meile seda nimekirja.
Järjestatud osa loetelu koosneb 4, 8 ja 15, ja
need elemendid on ikka sortimata.
Aga see lihtsalt nii juhtub, et järgmise sortimata element, 16,
on juba järjestatud.
Kuid seal on kuidagi meie algoritm teada, et 16
on juba oma õigesse asukohta, seega peame siiski
korrata täpselt sama protsessi.
Nii näeme, et 16 on väiksem kui 42, ja 16 on väiksem kui 23, nii
16 tuleb minimaalne element.
See on võimatu, et vahetada see element iseendaga, et saaksime
lihtsalt jätke see selles kohas.
Seega on meil vaja veel üht liigu meie algoritm.
42 on suurem kui 23, nii et 23 tuleb
miinimum sortimata element.
Kui me vahetada 23 ja 42, me lõpetame meie lõplik
järjestatud loetelu -
4, 8, 15, 16, 23, 42.
Me teame, 42 peab olema õiges kohas, sest see on
ainult element left, ja see on valik omamoodi.
Lähme nüüd ametlikuks meie algoritm mõned
pseudokoodi.
Liinil, näeme, et meil on vaja integreerida üle
iga element nimekirja.
Välja arvatud viimane osa, kuna 1 element
nimekiri on juba järjestatud.
Teisel liinil, arvame esimese osa sortimata
osa nimekirjas olevat minimaalne, nagu tegime meie
Näiteks, seega on meil midagi võrrelda.
Kolmas liin algab teine ​​silmus, kus me itereerime
iga sortimata element.
Me teame, et pärast i iteratsiooni, järjestatud osa
meie nimekirjas peab olema i elementidega sest iga samm
sorteerib üks element.
Nii et esimene sortimata element peab olema asendis i pluss 1.
On line neli, me võrrelda praegust element minimaalset
element, et oleme näinud siiani.
Kui praegune element on väiksem kui minimaalne
element, siis me mäletame praegune element nagu uus
miinimum on line viis.
Lõpuks liinidel kuue ja seitsme me swap minimaalne
elemendi esimese sortimata element, mis
lisades selle järjestatud osa nimekirjast.
Kui meil on algoritm, olulisem küsimus küsida
end programmeerijad on, kui kaua see veel kestab?
Me kõigepealt küsida, kui kaua see aega võtab selle
algoritm joosta halvimal juhul?
Meenutagem siinkohal me esindame see töötab
aega suur O notatsiooni.
Selleks, et määrata kindlaks minimaalne sortimata element, me
sisuliselt oli võrrelda iga element loendis
iga teine ​​element nimekirjas.
Intuitiivselt, see kõlab nagu O n ruudus operatsiooni.
Vaadates meie pseudokoodi, meil on ka loop pesitses sees
teine ​​silmus, mis tõesti kõlab nagu O
n ruudus operatsiooni.
Kuid pidage meeles, et me ei pea üle vaatama
kogu nimekirja määramisel miinimum sortimata element?
Kui me teadsime, et 4 oli järjestatud, näiteks me ei
vaja vaadata uuesti.
Kas see siis alumine sõiduaega?
Meie nimekirja pikkus 6, meil oli vaja teha viis
võrdlused esimese elemendi eest, neli võrdlust
Teine element, ja nii edasi.
See tähendab, et kogu sammude arv on summa
täisarvud 1 kuni pikkus nimekirja miinus 1.
Me ei esinda seda liitmise.
Me ei hakka kohtuvaidlust siin.
Aga selgub, et see liitmise on võrdne n korda
n miinus 1 üle 2.
Ehk samaväärselt, n ruudus üle 2 miinus n üle 2.
Rääkides asümptootilisest runtime, see n ruudus perspektiivis
läheb domineerima see n perspektiivis.
Nii et valik omamoodi on O n ruudus.
Tuletame meelde, et meie näites, valik omamoodi ikka vaja
kontrollida, kas arv, mis oli juba sorteeritud
vaja vedada.
See tähendab, et kui me jooksime valik omamoodi üle juba
järjestatud nimekirja, oleks vaja sama hulk meetmeid, mida ta
oleks sõites üle täiesti sortimata nimekirja.
Nii et valik omamoodi on parimal juhul täitmisel n ruudus,
mis me esindame omega n ruudus.
Ja see on see valik omamoodi.
Lihtsalt üks paljudest algoritme saame
kasutada sorteerida nimekirja.
Minu nimi on Tommy, ja see on cs50.