[Powered by Google Translate] [Täiendus Sorteeri]
[Tommy MacWilliam] [Harvardi Ülikool]
[See on CS50.TV]
Võtame pilk sisestamise sorteerida, algoritm võttes numbrite loendi ja sorteerimine neid.
Algoritm, pea meeles, on lihtsalt samm-sammult korra saavutamise ülesanne.
Põhiidee sisestamise sorteerida, on jagada oma nimekirja kaheks osaks,
järjestatud osa ja sorteerimata osa.
>> Igal sammul algoritm, number on teisaldatud
alates sortimata osal järjestatud osa
kuni lõpuks kogu nimekirja sorteeritakse.
Siin on nimekiri kuue sortimata numbrid - 23, 42, 4, 16, 8, ja 15.
Kuna need numbrid ei ole kõik tõusvas järjekorras, nad sortimata.
Kuna me ei ole alustatud sorteerimine veel, me kaaluma kõiki kuus elementi meie sorteerimata osa.
>> Kui hakkame sorteerimine, me paneme need järjestatud numbrite vasakul need.
Niisiis, alustame 23, esimene osa meie nimekirjas.
Meil ei ole ühtegi elementi meie järjestatud osa veel,
niiet lihtsalt kaaluda 23 olema alguse ja lõpu meie järjestatud osa.
Nüüd on meie järjestatud osa on üks arv, 23,
ja meie sorteerimata osa on need viis numbrit.
Lähme nüüd pane uus number meie sorteerimata osa, 42, arvesse järjestatud osa.
>> Selleks vajame võrrelda 42 kuni 23 - ainult osa meie järjestatud osa siiani.
Nelikümmend kaks on suurem kui 23, nii me lihtsalt lisada 42 kuni lõpuni
on järjestatud osa nimekirjast. Suurepärane!
Nüüd on meie järjestatud osa on kaheosaline ja meie sorteerimata osa on neli elementi.
Niisiis, oletame nüüd kolida 4 järgmine element sorteerimata osa.
Niisiis, kui peaks see olema paigutatud järjestatud osa?
>> Pea meeles, et me tahame panna selle numbri sorteeritud järjekorras
nii meie järjestatud osa jääb õigesti järjestatud üldse korda.
Kui me paneme 4 paremal 42, siis meie nimekirjas on rikkis.
Niisiis, oletame jätkata liigub paremalt vasakule meie omamoodi osa.
Nagu me liikuda, lähme minema iga numbri üles koht, et teha ruumi uue numbri.
Okei, 4 on ka vähem kui 23, nii et me ei saa pannakse see siin.
Liigume 23 õige koht.
>> See tähendab, et me tahaks panna 4 esimesse avasse järjestatud osa.
Märka, kuidas seda ruumi nimekirjas oli juba tühi,
sest me oleme liikunud järjestatud elemendid maha nagu me oleme kokku puutunud nendega.
Hea küll. Niisiis, me oleme poolel teel sinna.
Jätkame meie algoritm, lisades 16 arvesse järjestatud osa.
Kuusteist on alla 42, nii teeme vahetustega 42 paremale.
Kuusteist on ka vähem kui 23, nii teeme ka minema, et element.
>> Nüüd, 16 on suurem kui 4. Niisiis, tundub, et me tahaksime lisada 16 vahel 4 ja 23.
Liikudes läbi järjestatud osa nimekirja paremalt vasakule,
4 on esimene number oleme näinud, mis on väiksem kui arv
me üritame lisada.
Nii, nüüd saame sisestada 16 sellesse tühja pessa,
mis pidage meeles, et me oleme loonud liikuvat elementi sorteeri osa üle
nagu me oleme kokku puutunud nendega.
>> Hea küll. Nüüd oleme neli järjestatud elemendid ja kaks sorteerimata elemendid.
Nii, liigume 8 arvesse järjestatud osa.
Kaheksa on alla 42.
Kaheksa on alla 23.
Ja 8 on väiksem kui 16.
Aga 8 on üle 4.
Niisiis, me tahaksime lisada 8 vahel 4 ja 16.
Ja nüüd me lihtsalt veel üks element left sorteerida - 15.
Viisteist on väiksem kui 42,
Viisteist on alla 23.
Ja 15 on alla 16.
Aga 15 on suurem kui 8.
>> Nii, siin on koht, kus me tahame, et meie lõplik sisestamist.
Ja me oleme valmis.
Meil pole rohkem elemente sorteerimata osa,
ja meie järjestatud osa on õiges järjekorras.
Numbrid on reastatud väiksemast suuremani.
Niisiis, oletame, kui heita pilk mõned pseudokoodi, mis kirjeldab samme me lihtsalt läbi.
>> On line 1 näeme, et me peame itereerima üle iga elemendi nimekirja
välja arvatud esimene, sest esimene osa sorteerimata osa lihtsalt muutunud
esimene element järjestatud osa.
Ridadel 2 ja 3, me kursis hoida meie praegune koht sorteerimata osa.
Element tähistab arvu me praegu liigume järjestatud osa,
ja j esindab meie indeks sorteerimata osa.
>> On line 4, me itereerimise läbi järjestatud osa paremalt vasakule.
Me soovime peatada itereerimise kui element vasakul meie praegune asukoht
on väiksem kui element me üritame lisada.
Real 5, me nihkub iga element kohtame ühe sammu paremale.
Nii on meil selge ruumi lisada, kui leiame esimese elemendi
vähem kui element me liigume.
Real 6 uuendame me oma counter jätkuvalt liikuda vasakule läbi järjestatud osa.
Lõpuks on line 7, me lisada element järjestatud osa nimekirjast.
>> Me teame, et see on okei lisada positsiooni j,
sest me oleme juba liikunud element, mis varem seal ühe sammu paremale.
Pea meeles, et me liigume läbi järjestatud osa paremalt vasakule,
kuid me liigume läbi sorteerimata osa vasakult paremale.
Hea küll. Olgem nüüd pilk kui kaua töötab, et algoritm võttis.
Me kõigepealt küsida, kui kaua see aega võtab selle algoritmi joosta halvimal juhul.
Tuletame meelde, et me esindame see sõiduaega Big O notatsiooni.
Selleks, et sorteerida meie nimekirjas, me pidime itereerime elemendid sorteerimata osa,
ja iga neid elemente, potentsiaalselt üle kõik elemendid järjestatud osa.
Intuitiivselt, see kõlab nagu O (n ^ 2) operatsiooni.
>> Vaadates meie pseudokoodi, meil on silmus Pesastatud sees teise silmuse,
mis tegelikult kõlab O (n ^ 2) operatsiooni.
Kuid järjestatud osa loetelu ei sisaldanud kogu nimekirja kuni lõpuni.
Siiski, me võiks lisada uus element alguses on järjestatud osa
iga iteratsiooni algoritm,
mis tähendab, et me tahaks olla vaadata iga element praegu järjestatud osa.
Niisiis, see tähendab, et me võiks teha ühe võrdlus teise elemendi,
kaks võrdlust kolmandat elementi, ja nii edasi.
Niisiis, trepiastmete arv on summa täisarvud 1 kuni pikkus nimekirja miinus 1.
Me ei esinda seda liitmise.
>> Me ei hakka kohtuvaidlust siin, aga tuleb välja, et see liitmise võrdub
n (n - 1) rohkem kui 2, mis on võrdne n ^ 2/2 - n / 2.
Rääkides asümptootilisest runtime,
see n ^ 2 perspektiivis läheb domineerima see n perspektiivis.
Nii sisestamise sorteerida on Big O (n ^ 2).
Mis siis, kui me jooksime sisestamise järgi Sorteerida juba järjestatud nimekirja.
Sel juhul me lihtsalt luua järjestatud osa vasakult paremale.
Niisiis, me vaid vajadus tellimusel n samme.
>> See tähendab, et sisestamise omamoodi on parimal juhul täitmisel n,
mis me esindame koos Ω (n).
Ja ongi sisestamise sorteerida,
lihtsalt üks paljudest algoritme saame kasutada sorteerida nimekirja.
Minu nimi on Tommy, ja see on CS50.
[CS50.TV]
Oh, sa lihtsalt ei saa lõpetada, et kui ta hakkab.
Oh, me tegime seda - >> Boom!