>> [Muusika mängib]
>> ZAMYLA Chan: Esimene asi, mida võiks teadet leid on see, et meil on juba
on kood kirjutatud meile.
Seda nimetatakse jaotus koodi.
Nii et me ei ole ainult kirjalikult oma koodi nullist enam.
Pigem me täidame tühjad mõnes olemasoleva koodi.
>> Find.c programm küsib numbrid täita heinakuhjas, otsib
heinakuhjas kasutajale esitatud nõel, ja ta teeb seda, kutsudes sorteerida ning
Otsingu funktsioonid määratletud aastal helpers.c.
Nii find.c on kirjutatud juba.
Sinu ülesanne on kirjutada abilised.
>> Niisiis, mida me teeme?
Me rakendamisel kaks ülesannet.
Search, mis tagastab tõene kui väärtus leitakse heinakuhjas, tagasi
false, kui väärtus on ei heinakuhjas.
Ja siis me ka rakendatakse sort mis sordib massiivi nimetatakse väärtused.
>> Teeme tegeleda otsing.
Otsi praegu rakendatakse lineaarne otsida, kuid mida saate teha palju
paremini.
Linear otsing rakendatakse O n ajal, mis on üsna aeglane.
Kuigi see võib otsida Suvalise loendi talle antud.
Sinu ülesanne on viia ellu binaarne otsing, mis on otsa aeg O log n.
See on päris kiire.
>> Aga seal on klausel.
Binary otsing vaid otsida läbi eelnevalt sorteeritud nimekirja.
Miks see nii on?
>> Noh vaatame näiteks.
Kuna massiivi väärtusi, heinakuhjas, me otsima
nõela.
Ja selles näites täisarv kolm.
Nii, et binaarne otsing toimib on see, me võrdleme keskel väärtus
massiivi nõela meelega kuidas avasime telefoniraamat keskel
lehekülje nädal null.
>> Nii et pärast võrreldes keskmise väärtuse nõel, võite visata kas
vasakule või paremale poole massiivi pingutades oma piire.
Sel juhul, kuna kolm meie nõela on väiksem kui 10, keskväärtusena,
seonduv õigus võib väheneda.
Aga proovi teha oma piire nii range kui võimalik.
Kui keset väärtus ei ole nõela siis sa tead, et sa ei pea
lisada selle oma otsingut.
Nii et sa oled õiges seotud ei pinguta otsi piire natukene rohkem,
ja nii edasi ja nii edasi, kuni leiad nõela.
>> Mis siis pseudokoodi välja näeb?
Noh, kui me otsime veel läbi nimekirja ja veel elemente
vaata, me keskel nimekirja ja võrrelda seda keset väärtust
meie nõel.
Kui nad võrdsed, siis see tähendab, et me oleme leidsin nõela ja suudame
tagasi true.
>> Vastasel juhul, kui nõel on alla keskel väärtus, siis see tähendab, et me
ära visata paremal poolel, ja lihtsalt search vasakul massiiv.
Vastasel juhul me kontrollime paremal pool massiivi.
Ja lõpuks, kui sa ei ole üldse rohkem elemente vasakule otsida aga sa
ei ole leidnud oma nõela veel, siis tagasi false sest nõel
kindlasti ei ole heinakuhjas.
>> Nüüd puhas asi see pseudokoodi aastal Kahendotsingupuu on, et see võib olla
tõlgendada kas iteratiivne või rekursiivne rakendamine.
Seega oleks rekursiivne kui sa helistasid otsingu funktsiooni otsing
toimida kas pooles massiivi.
Me katame rekursioon veidi hiljem muidugi, aga tean, et see on
valik, kui soovite, et proovida.
>> Nüüd vaatame sort.
Sort võetakse massiivi ja täisarv n, mis on suuruse massiivi.
Nüüd on mitmeid erinevaid kehvasti, ja saate vaadata mõned
püksid demos ja selgitused.
Tagasipöördumise tüüp meie funktsioon on tühine.
See tähendab, et me ei lähe tagastama array sort.
Me tegelikult muudame väga massiiv, mis oli läinud meile.
>> Ja see on võimalik, sest massiivid on möödunud viitena C. Nüüd me
vaata rohkem sellest hiljem, kuid oluline vahe möödaminnes
midagi nagu täisarv ja mööduv massiiv, on see, et kui sa
pass täisarv, C on lihtsalt läheb koopia teha, et täisarv ja liigu
seda funktsiooni.
Originaal muutuja ei muutu kui funktsioon on lõppenud.
Reis massiivi, teiselt poolt, on see ei kavatse teha koopia ja sa
tegelikult toimetamine väga massiiv ise.
>> Nii üht tüüpi sort on valik sort.
Valiku sort töötab alates aasta alguses, ja siis kinnitada,
üle ja leida kõige väiksem element.
Ja siis vaheta see väiksema elemendi esimene.
Ja siis liikuda teise elemendi , Leida järgmise väikseim
element ja seejärel vahetada, et koos teine ​​element massiivi sest
Esimene element on juba järjestatud.
Ja nii siis jätkub kõik element väljaselgitamisel väikseim
väärtus ja vahetada see välja.
>> Sest ma võrdub 0, kõige esimene element kuni n miinus 1, sa lähed, et võrrelda
iga järgnev väärtus pärast seda ja leiavad indeksi minimaalne väärtus.
Kui leiate minimaalse väärtuse indeksi saab vahetada, et väärtus massiivi
miinimum ja array I.
>> Teist tüüpi sort, mida saate rakendamiseks on mull sort.
Nii mull omamoodi kordab üle nimekirja võrreldes külgnevate elementide ja
vahetada elemente on vales järjekorras.
Ja sel viisil, suurima elemendi tahe mull lõpuni.
Ja nimekiri on sorteeritud kord enam elemendid on vahetatud.
>> Nii et need on kaks näidet sort algoritme, mis saab rakendada
Leia programm.
Kui olete sorteerida ning olete teha otsing, sa oled valmis.
Minu nimi on Zamyla ja see on CS50.
>> [Muusika mängib]