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