[Powered by Google Translate] [Mull sorteerida]
[JACKSON STEINKAMP Harvardi Ülikool]
[See on CS50. CS50TV]
Mull sorteerida on näide sortimise algoritm -
see tähendab, et kord sorteerimine komplekt elemendid
kasvavas või kahanevas järjekorras.
Näiteks kui sa tahad sortida massiivi koosneb numbrid
[3, 5, 2, 9], nõuetekohase rakendamise mull sorteerida Jõutakse
sorteeritud massiiv [2, 3, 5, 9] tõusvas järjekorras.
Nüüd ma lähen selgitada pseudokoodi kuidas algoritm töötab.
>> Oletame, et me sorteerimine nimekiri 5 täisarvud - 3, 2, 9, 6, ja 5.
Algoritm algab vaadates kaks esimest elementi, 3 ja 2,
ja kontrollida, kas nad on rikkis üksteise suhtes.
Nad on - 3 on suurem kui 2.
Et olla tõusvas järjekorras, peaksid nad olema teistpidi.
Niisiis, me vahetada neid.
Nüüd nimekiri näeb välja selline: [2, 3, 9, 6, 5].
>> Järgmiseks vaatame teist ja kolmandat elementi, 3 ja 9.
Nad on õiges järjekorras üksteise suhtes.
See on, 3 on alla 9 nii algoritm ei vahetada neid.
Järgmiseks vaatame 9 ja 6. Nad on rikkis.
>> Niisiis, me peame vahetada neid, sest 9 on suurem kui 6.
Lõpuks vaatleme viimase kahe täisarvu, 9 ja 5..
Nad on rikkis, nii et nad tuleb vahetada.
Pärast esimest täielik läbivad nimekirja,
see näeb välja selline: [2, 3, 6, 5, 9].
Pole paha. See on peaaegu järjestatud.
Aga meil on vaja joosta nimekirja uuesti, et saan seda täiesti sorteerida.
Kaks on alla 3, nii et me ei vahetada neid.
>> Kolm on väiksem kui 6, nii et me ei vahetada neid.
Kuus on suurem kui 5. Me vahetasid.
Kuus on alla 9. Me ei vaheta.
Pärast teist läbida, see näeb välja selline: [2, 3, 5, 6, 9]. Perfect.
Nüüd saab kirjutada seda pseudokoodi.
Põhimõtteliselt iga element nimekirjas, me peame vaatama seda
ja osa otse oma õigust.
Kui nad on rikkis üksteise suhtes - see tähendab, kui element vasakul
on suurem kui üks paremal - peaksime swap kaks elementi.
>> Me teeme seda iga element nimekiri, ja me oleme teinud ühe läbida.
Nüüd lihtsalt pead tegema läbipääs piisavalt korda, et tagada nimekirja
täielikult, õigesti järjestatud.
Aga mitu korda me peame läbima nimekirja
garanteerida, et me oleme valmis?
Noh, halvimal juhul on see, kui meil on täiesti tagurpidi nimekirja.
Siis kulub mitu läbivad läbi ekspordi hulk on võrdne
elementide n-1.
Kui see ei ole mõtet intuitiivselt, mõtlevad lihtne juhtum - nimekiri [2, 1].
>> See saab olla üks läbipääs sorteerida õigesti.
[3, 2, 1] - halvimal juhul on see, et 3 elementi järjestatud tahapoole,
see saab võtta 2 korduste omamoodi.
Pärast ühe iteratsiooni, see [2, 1, 3].
Teine saagikus sorteeritud massiiv [1, 2, 3].
Nii et sa tead, sa ei pea minema läbi massiivi üldiselt
rohkem kui n-1 korda, kus n on elementide arv massiivis.
Seda nimetatakse mull sorteerida, sest suurim elemendid kipuvad "mull-up"
paremale päris kiiresti.
Tegelikult on see algoritm on väga huvitav käitumine.
>> Pärast m korduste kaudu kogu antennide massiivi,
parempoolsem m elemendid on tagatud
välja sorteerida oma õigesse kohta.
Kui soovite seda ise nägema,
saame proovida seda täiesti tagurpidi nimekiri [9, 6, 5, 3, 2].
Pärast ühte läbivad kogu nimekirja,
[Heli kirjutamiseks]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
parempoolsem 9. osa on tema õige koht.
Pärast teist läbipääs, 6 on "mullidena üles", et
2. parempoolsem koht.
Kahest elemendist paremal - 6 ja 9 - on nende õiged kohad
Pärast kahte esimest liigu läbi ekspordi.
>> Niisiis, kuidas me saame kasutada seda optimeerida algoritm?
Noh, pärast ühe iteratsiooni kaudu massiivi
me tegelikult ei vaja, et kontrollida parempoolsem osa
sest me teame, see on järjestatud.
Pärast kaks iteratsiooni, mida me teame kindlasti parempoolsem kaks elementi on olemas.
Niisiis, üldiselt pärast k korduste kaudu kogu massiiv,
kontrollides viimase k elementi on ülearune, sest me teame
nad õiges kohas juba.
>> Seega, kui olete sorteerimine massiivi n elementi,
aasta esimese iteratsiooni - you'll on sorteerida kõik elemendid - esimene n-0.
Teisel iteratsiooni, sa pead vaatama kõiki elemente, kuid viimasel -
esimese n-1.
Teine optimeerimine võib olla kontrollida, kas nimekiri on juba järjestatud
pärast iga iteratsiooni.
Kui see on juba järjestatud, meil ei ole vaja teha enam kordustes
nimekiri läbi.
Kuidas me saame seda teha?
Noh, kui me ei tee vahetustehingute läbipääs nimekirja,
on selge, et loetelu on juba järjestatud, sest me ei vaheta midagi.
Nii et me kindlasti ei pea sortida jälle.
>> Äkki saab initsialiseerida lipu muutuja nimega "sorteerimata", et
vale ja muuda see tõsi, kui teil on vahetada mis tahes elementide
ühe iteratsiooni kaudu massiivi.
Või samamoodi teha loenduri loendama, kui paljud vahetustehingud teete
igal konkreetsel iteratsiooni.
Lõpus iteratsiooni, kui te ei vaheta tahes osades,
sa tead, et loend on juba sorteeritud ja sa oled teinud.
Mull sorteerida, nagu ka teised sorteerimise algoritme, võib olla
Tweaked tööle ühtki asjaolu, mis on tellimise meetodit.
>> See tähendab, et antud kaks elementi teil on võimalus öelda kui esimene
on üle, on võrdne või väiksem kui teine.
Näiteks võid sorteerida tähestiku öeldes
et a <b, b <c, jne
Või võite sortida nädalapäevade kus pühapäeval on vähem kui esmaspäev
mis on vähem kui teisipäeval.
>> Bubble Sort ei ole sugugi väga tõhus või kiire sortimise algoritm.
Selle halvima runtime on Big O n ²
sest sa pead tegema n iteratsiooni kaudu nimekirja
kontrollides kõik n elementi iga läbipääs, nxn = n ².
See läbijooksuaeg tähendab, et kui mitu elementi sa sorteerimine suureneb,
läbijooksuaeg suurendab quadratically.
>> Aga kui efektiivsust ei ole suur mure oma programmi
või kui sa oled ainult sorteerimine vähe elemente,
te võite leida mull sorteerida kasulik, sest
see on üks lihtsamaid sorteerimine algoritme mõista
ja kood.
See on ka suurepärane võimalus saada kogemusi tõlkimise teoreetiline
algoritm arvesse tegelikku toimimist kood.
Noh, see on mull sorteerida teile. Täname vaadates.
CS50.TV