Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [BUBBLE SORT]
[JACKSON Steinkamp Harvardin yliopisto]
[Tämä on CS50. CS50TV]
Bubble Lajittele on esimerkki lajittelu algoritmi -
joka on, menettely lajittelua joukon elementtejä
nousevassa tai laskevassa järjestyksessä.
Esimerkiksi, jos halusi lajitella taulukon koostuu numeroiden
[3, 5, 2, 9] asianmukaisen täytäntöönpanon Bubble Lajittele palaisi
lajiteltu array [2, 3, 5, 9] nousevassa järjestyksessä.
Nyt aion selittää pseudokoodilla miten algoritmi toimii.
>> Sanotaan olemme lajittelu luettelo 5 kokonaislukujen - 3, 2, 9, 6, ja 5.
Algoritmi alkaa tarkastelemalla kahden ensimmäisen osan, 3 ja 2,
ja tarkistaa jos he epäkunnossa suhteessa toisiinsa.
Ne ovat - 3 on suurempi kuin 2.
Oltava nousevassa järjestyksessä, ne olisi toisinpäin.
Joten me vaihtaa niitä.
Nyt näyttää tältä: [2, 3, 9, 6, 5].
>> Seuraavaksi tarkastellaan toisen ja kolmannen elementtejä, 3 ja 9.
He ovat oikeassa järjestyksessä toistensa suhteen.
Se on, 3 on vähemmän kuin 9, joten algoritmi ei vaihtaa niitä.
Seuraavaksi katsomme 9 ja 6. He epäkunnossa.
>> Joten meidän täytyy vaihtaa niitä, koska 9 on suurempi kuin 6.
Lopuksi katsomme viimeisen kahden kokonaisluvun, 9 ja 5.
He epäkunnossa, joten ne on vaihdettu.
Kun ensimmäinen täydellinen läpi listan,
se näyttää tältä: [2, 3, 6, 5, 9].
Ei paha. Se on melkein lajiteltu.
Mutta meidän täytyy käydä läpi listan uudelleen saada se täysin lajiteltu.
Kaksi alle 3, joten emme vaihda niitä.
>> Kolme on alle 6, joten emme vaihda niitä.
Kuusi on suurempi kuin 5. Me vaihdettu.
Kuusi on alle 9. Emme vaihda.
Kuluttua toisesta läpi, se näyttää tältä: [2, 3, 5, 6, 9]. Perfect.
Nyt, kirjoita se pseudokoodilla.
Periaatteessa jokaisen elementin luettelossa, meidän on tarkasteltava sitä
ja elementti suoraan sen oikealle.
Jos ne ovat epäkunnossa toistensa suhteen - se on, jos elementti vasemmalla
on suurempi kuin yksi oikea - meidän pitäisi vaihtaa kaksi elementtiä.
>> Teemme tämän jokaisen elementin listan, ja olemme tehneet yhden läpimenon.
Nyt vain täytyy tehdä läpiviennin tarpeeksi monta kertaa varmistamaan luetteloon
täysin asianmukaisesti järjestetty.
Mutta kuinka monta kertaa meillä on läpi luettelon
taata, että olemme tehneet?
No, pahimmassa tapauksessa on, jos meillä on täysin taaksepäin luettelosta.
Sitten se otetaan useita pass-through yhtä suuri
elementtien n-1.
Jos tämä ei ole järkeä intuitiivisesti ajatella yksinkertaisen asian - luettelon [2, 1].
>> Tämä tulee ottaa yksi pass-through lajitella oikein.
[3, 2, 1] - Pahimmassa tapauksessa on, että 3 elementit lajitellaan taaksepäin,
se tulee ottaa 2 iteraatioiden lajitella.
Jälkeen yhden iteraation, se on [2, 1, 3].
Toisen saannot lajiteltu array [1, 2, 3].
Joten tiedät et koskaan tarvitse käydä läpi array, yleensä
enemmän kuin n-1 kertaa, missä n on elementtien lukumäärä jono.
Sitä kutsutaan Bubble Järjestä koska suurin osa taipumus "kupla-up"
oikealle melko nopeasti.
Itse asiassa, tämä algoritmi on erittäin mielenkiintoinen käyttäytymistä.
>> Kun m toistojen kautta koko jono,
oikeanpuoleisin m elementit on taattu
voidaan lajitella niiden oikeaan paikkaan.
Jos haluat nähdä tämän itse,
Voimme kokeilla sitä täysin taaksepäin luettelon [9, 6, 5, 3, 2].
Yhden läpi koko luettelon,
[Ääni kirjallisesti]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
oikeanpuoleisin elementti 9 on oikeassa paikassa.
Kun toinen pass-through, 6 on "kuplina ylös-ja
toinen oikeanpuoleisin paikka.
Kaksi elementtiä oikealla - 6 ja 9 - tulee oikeisiin paikkoihin
kahden ensimmäisen pass-through.
>> Joten, kuinka voimme käyttää tätä optimoida algoritmin?
No, kun yhden iteraation läpi array
emme oikeastaan tarvitse tarkistaa oikeanpuoleisin elementti
koska tiedämme, että se on lajiteltu.
Kahden iteraatiota, tiedämme varmasti oikeanpuoleisin kaksi elementtiä ovat olemassa.
Niin, yleensä sen jälkeen, kun k: n iteraation läpi täyden valikoiman,
tarkkailun viimeinen k alkiota on tarpeeton, koska tiedämme
he ovat oikeassa paikassa jo.
>> Joten jos olet lajittelua joukko n alkiota,
ensimmäisen iteraation - you'll tarvitse lajitella kaikki elementit - ensimmäinen n-0.
Toisessa iteraatio, sinun täytyy katsoa kaikki elementit, mutta viimeinen -
ensimmäisen n-1.
Toinen optimointi voisi olla tarkistaa, jos lista on jo järjestetty
jokaisen iteraation.
Jos se on jo lajiteltu, meidän ei tarvitse tehdä enää toistojen
Selaa luetteloa.
Miten voimme tehdä tämän?
No, jos emme tee mitään vaihtamisen pass-through luettelon,
on selvää, että luettelo on jo järjestetty, koska emme vaihda mitään.
Joten me varmasti ei tarvitse lajitella uudelleen.
>> Ehkä voisit alustaa lippu muuttuja nimeltä "ei lajiteltu 'to
vääriä ja vaihda se totta, jos sinulla on vaihtaa mitään elementtejä
yhden iteraation avulla jono.
Tai vastaavasti tehdä laskurin laskemaan kuinka monta swap teet
tiettynä iterointia.
Lopussa iteraation, jos et vaihtaa mitään osia,
tiedät luettelo on jo lajiteltu ja olet valmis.
Bubble lajittelet, kuten muutkin lajittelualgoritmeja, voi olla
viritetty toimimaan kaikkien elementtien joiden tilaaminen menetelmällä.
>> Eli annetaan kaksi elementtiä sinulla tapa sanoa, jos ensimmäinen
on suurempi kuin, yhtä suuri tai pienempi kuin toinen.
Esimerkiksi, voit lajitella aakkosten sanomalla
että a Bubble Järjestä ei suinkaan erittäin tehokas tai nopea lajittelua algoritmi.
Sen pahin runtime on Big O n ²
koska sinun täytyy tehdä n toistojen kautta listan
Tarkistamme kaikki n alkiota kussakin pass-through, nxn = n ².
Tämä ajoaika tarkoittaa sitä, että elementtien lukumäärä olet lajittelu kasvaa,
käyntiaika kasvaa neliöllisesti.
>> Mutta jos tehokkuus ei ole suuri huolenaihe ohjelman
tai jos olet vain lajittelu pieni joukko tekijöitä,
saatat löytää Bubble Lajittele hyödyllinen, koska
se on yksi yksinkertaisimmista lajittelualgoritmeja ymmärtää
ja koodi.
Se on myös hyvä tapa saada kokemusta kääntämisestä teoreettinen
algoritmi osaksi varsinaisen toiminnan koodia.
No, Bubble Lajittele sinulle. Kiitos katsomassa.
CS50.TV