>> [Muusika mängib]
DOUG LLOYD: Okei, nii et mull sorteerida on algoritmi
saate sortida elementide kogum.
Võtame vaatame, kuidas see toimib.
>> Nii põhiidee mull sorteerida on see.
Me üldiselt tahavad liikuda kõrgema väärtustatud elemendid üldiselt õige,
ja alandada hinnatud elemendid üldiselt vasakule, nagu me ootaks.
Me soovime, et väiksem asju olla Alguses ja kõrgema asju
olema lõpus.
>> Kuidas me seda teeme?
Noh pseudokoodi koodi võib öelda, olgem
määrata swap vastuollu nullist väärtus.
Me näeme, miks me seda teeme teise.
Ja siis me kordame järgmist protsessi, kuni swap counter on 0,
või kuni me ei tee vahetustehingud üldse.
>> Taasta swap vastuollu 0, kui see ei ole juba 0.
Siis vaadata igal kõrvutistest elemente.
Kui need kaks tegurit on mitte selleks, vahetada neid,
ja lisatakse 1 swap counter.
Kui sa mõtled seda enne visualiseerida seda,
märgata, et see liigub madalama väärtustatud elemendid vasakul
ja väärtuslikumateks elemendid paremal, efektiivselt seda, mida me tahame teha,
mis on liikuda nende rühmade elementide niimoodi.
Olgem visualiseerida, kuidas seda võiks vaadata kasutades meie massiivi
et me testimiseks kasutatud neid algoritme.
Meil on sorteerimata massiivi siin jälle, tähistatud kõik elemendid
on punane.
Ja ma pöörasin oma swap counter nonzero väärtus.
Ma suvaliselt valisid negatiivne 1-- see ei ole 0.
Me tahame, et korrata seda protsessi kuni swap counter on 0.
See on põhjus, miks ma panen oma swap vastuollu mõne nullist väärtus,
sest vastasel korral swap counter oleks 0.
Me isegi ei hakata protsessi algoritmi.
Nii jälle sammud are-- reset swap counter
0, siis vaatame iga külgnevate paar, ja kui nad on rikkis,
vahetada neid ja lisada 1 konverteerimist counter.
Nii alustagem seda protsessi.
Nii et esimene asi, mida me teeme on seadsime swap vastuollu 0,
ja siis hakkame otsima igal kõrvutistest.
>> Nii me esimest korda hakata otsima 5 ja 2.
Me näeme, et nad on välja tellida ja nii me vahetada neid.
Ja lisame 1 konverteerimist counter.
Nüüd meie swap counter on 1, ja 2 ja 5 on sisse lülitatud.
Nüüd korrake protsessi uuesti.
>> Me vaatame järgmise kõrvutistest, 5 ja 1-- nad ka rikkis,
nii et me vahetada neid ja lisada 1 konverteerimist counter.
Siis vaatame 5 ja 3.
Nad on rikkis, nii et me vahetada neid ja lisame 1 konverteerimist counter.
Siis vaatame 5 ja 6.
Nad on selleks, et me ei ole tegelikult vaja vahetada midagi seekord.
Siis vaatame 6 ja 4.
Nad on ka korrast ära, nii et me vahetada neid ja lisame 1 konverteerimist counter.
>> Nüüd pane tähele, mis juhtus.
Me oleme liikunud 6 kogu tee lõpuni.
Nii valikut omamoodi, kui olete näha, et video, mida me tegime oli
oleme jõudnud liigutades Väikseim elemendid hoone
sorteeritud massiiv peamiselt vasakult paremale, väiksemast ja lõpetades suuremaga.
Juhul mull sorteerida, kui me oleme pärast seda eriti algoritm,
me tegelikult läheb ehitama sorteeritud massiivi õigus
vasakule, suuremast väiksema.
Oleme efektiivselt mullidena 6 suurima väärtuse, kõik viis kuni lõpuni.
>> Ja nii me nüüd tunnistada et mis on järjestatud,
ja tulevikus iterations-- läbimas massiivi again--
me ei pea arvestama 6 enam.
Meil on ainult kaaluda sorteerimata elemendid
Kui me vaatame kõrval paari.
Nii oleme valmis ühe läbida mull omamoodi.
Nüüd me läheme tagasi küsimuse juurde, korrata, kuni swap counter on 0.
Noh swap counter on 4, nii et me ei kavatse
hoida korrates seda protsessi uuesti.
>> Me läheme nullida swap counter 0, ja vaadata iga kõrvutistest.
Nii hakkame koos 2 ja 1-- nad rikkis, nii et me vahetada neid
ja lisame 1 konverteerimist counter.
2 ja 3, et nad on korras.
Meil ei ole vaja midagi teha.
3 ja 5 on korras.
Meil ei ole vaja midagi teha seal.
>> 5 ja 4, on nad läbi tellimuse, ja nii me
vaja vahetada neid ja lisada 1 konverteerimist counter.
Ja nüüd me oleme liikunud 5, suuruselt järgmine element,
lõpuni sorteerimata portsjonina.
Nii saame helistada, et osa järjestatud osa.
>> Nüüd sa vaadata ekraan ja ilmselt võib öelda,
kui ma saan, et massiivi on järjestatud just nüüd.
Aga me ei saa tõendada, et veel.
Meil ei ole garantii et see on järjestatud.
Aga see on koht, kus swap counter läheb mängu tulla.
>> Nii et me oleme valmis läbima.
Swap-counter on 2.
Nii et me läheme kordama Selle protsessi uuesti,
korrata, kuni swap counter on 0.
Taasta swap vastuollu 0.
Nii me lähtestada.
>> Nüüd vaatame iga kõrvutistest.
See on selleks, 1 ja 2.
2 ja 3 on selleks.
3 ja 4 on selleks.
Nii sel hetkel, märkate oleme valmis vaadates iga kõrvutistest,
kuid swap counter on ikka 0.
>> Kui me ei ole minna mis tahes elemente, siis nad
peab olema selleks, mida Tänu sellele protsessile.
Ja nii kasutegur kehvasti, et me arvuti teadlased armastan,
on meil nüüd kuulutada kogu massiiv tuleb
sorteerida, sest me ei on vahetada mistahes elemente.
See on päris kena.
>> Mis siis halvimal juhul stsenaarium mull omamoodi?
Halvimal juhul massiiv on täiesti vastupidises järjekorras,
ja nii me peame mull iga Suure elemendid kõik
Muide kogu massiivi.
Ja me tegelikult ka on mull kõik väikesed elemendid tagasi
kõik teed kogu massiivi, liiga.
Nii iga n elemendid on liikuda kõigis teiste n elemente.
Nii et halvimal juhul.
Parimal juhul stsenaariumi küll, see on
veidi erinev valikut omamoodi.
Massiiv on juba järjestatud, kui me minema.
Me ei pea tegema mingeid vahetustehingute esimene pass.
Nii et me oleks võinud vaadata kell vähem elemente, eks?
Me ei pea kordama seda töödelda mitmeid kordi.
>> Mida see tähendab?
Mis siis halvimal juhul mull sorteerida ning millised on
Parimal juhul mull omamoodi?
Kas sa vist seda?
Halvimal juhul pead itereerima kõigis n elemendid n korda.
Nii et halvimal juhul on n ruudus.
>> Kui massiiv on täiesti sorteeritud aga sa ainult
on vaadata iga elementide üks kord.
Ja kui swap counter on ikka 0, sa ei saa öelda, see massiiv on järjestatud.
Ja nii parimal juhul on see tegelikult parem kui valikut
sort-- see omega n.
>> Ma olen Doug Lloyd.
See on CS50.