[Musiikkia] DOUG Lloyd: Selvä, joten kuplalajittelu on algoritmi voit lajitella joukko elementtejä. Katsotaanpa katsomaan miten se toimii. 

Joten perusajatuksena kuplalajittelu on tämä. Me yleensä haluavat siirtyä korkeammalle arvosti yleensä oikealle, ja laske arvosti yleisesti vasemmalle, kun odotamme. Haluamme alempi asiat olevan alussa, ja korkeampi asiat olla lopussa. 

Miten teemme tämän? Hyvin pseudokoodilla koodi, voisimme sanoa, katsotaanpa asettaa swap laskuri muu kuin nolla. Näemme miksi me teemme, että toinen. Ja sitten toistamme seuraavat kunnes swap laskuri on 0, tai kunnes teemme mitään swap lainkaan. 

Nollaa swap laskuri 0 jos se ei ole jo 0. Sitten katsoa joka vierekkäisen parin elementtejä. Jos nämä kaksi tekijää ovat ei kunnossa, vaihtaa niitä, ja lisätään 1 swap laskuri. Jos olet ajatellut tämä ennen kuin visualisoida sitä, huomaa, että tämä siirtyy alemman arvosti vasemmalle ja korkeampi arvosti oikealle, tehokkaasti tehdä mitä haluamme tehdä, joka on siirtää nämä ryhmät elementtien tavoin. Katsotaanpa visualisoida miten tämä voisi näyttää käyttämällä array että me testata nämä algoritmit. Meillä lajittelematonta joukko täällä taas, merkitty kaikki elementit on punaisella. Ja minä käänsin swap laskuri on nollasta poikkeava arvo. I mielivaltaisesti Valitsin negatiivinen 1-- se ei ole 0. Haluamme toistaa tämän prosessin kunnes swap laskuri on 0. Siksi minä asetan swap vastoin joitakin ei-nolla, koska muuten swap laskuri olisi 0. Olisimme edes alkaa prosessi algoritmin. Joten jälleen vaiheet are-- Nollaa swap laskuri 0, sitten katsoa joka vieressä pari, ja jos he epäkunnossa, vaihtaa niitä, ja lisää 1 swap laskuri. Aloitetaanpa tässä prosessissa. Joten ensimmäinen asia mitä teemme on asetamme swap laskuri 0, ja sitten me alkaa etsiä jokaisen vierekkäisen parin. 

Joten ensin alkaa katsella 5 ja 2. Näemme, että he ovat poissa tilata ja niin me vaihtaa niitä. Ja lisäämme 1 swap laskuri. Joten nyt meidän swap laskuri on 1, ja 2 ja 5 on kytketty. Nyt toista prosessi uudelleen. 

Katsomme seuraavaksi vierekkäisten, 5 ja 1-- he ovat myös epäkunnossa, joten me vaihtaa niitä ja lisätä 1 swap laskuri. Sitten katsomme 5 ja 3. Ne ovat epäkunnossa, joten swap niitä ja lisäämme 1 swap laskuri. Sitten katsomme 5 ja 6. He järjestyksessä, joten emme oikeastaan täytyy vaihtaa mitään tällä kertaa. Sitten katsomme 6 ja 4. Ne ovat myös epäkunnossa, joten swap niitä ja lisäämme 1 swap laskuri. 

Nyt huomaa, mitä on tapahtunut. Olemme siirtyneet 6 aina loppuun. Joten valinta lajitella, jos olet nähdä, että video, mitä teimme oli päädyimme liikkuva pienin elementtejä rakentamisessa lajitellut array olennaisesti vasemmalta oikealle, pienimmästä suurimpaan. Kun kyseessä on kuplalajittelu, jos olemme seuraa tätä tiettyyn algoritmiin, olemme todella aiotaan rakentaa lajitellut array oikealta vasemmalle, suurimmasta pienimpään. Olemme tehokkaasti kuplia 6, Suurin arvo, aina loppuun. 

Ja jotta voimme nyt julistaa että lajitellaan, ja tulevaisuudessa iterations-- läpi array again-- meillä ei tarvitse harkita 6 enää. Meillä vain on otettava huomioon lajittelemattomat elementit kun etsimme viereisillä paria. Joten olemme lopettaneet yksi läpi kuplalajittelu. Joten nyt palaamme kysymykseen, Toista, kunnes swap laskuri on 0. No swap laskuri on 4, joten olemme menossa pitää toistaa tämän prosessin uudelleen. 

Aiomme palauttaa swap laskuri 0, ja näyttää jokaisen vierekkäisen parin. Joten aloitamme 2 ja 1-- he epäkunnossa, joten me vaihtaa niitä ja lisäämme 1 swap laskuri. 2 ja 3, he ovat kunnossa. Meidän ei tarvitse tehdä mitään. 3 ja 5 ovat kunnossa. Meidän ei tarvitse tehdä mitään siellä. 

5 ja 4, ne ovat poissa järjestyksen, ja niin me täytyy vaihtaa niitä ja lisätä 1 swap laskuri. Ja nyt olemme siirretty 5, seuraavaksi suurin elementti, loppuun lajittelemattoman osan. Joten voimme nyt kutsua että osa lajiteltu osan. 

Nyt etsit näyttö ja luultavasti voi kertoa, kuten voin, että jono lajitellaan juuri nyt. Mutta emme voi todistaa, että vielä. Meillä ei ole takeita että se on lajiteltu. Mutta tämä on silloin swap laskuri tulee kuvaan. 

Joten olemme valmiiksi omille. Swap laskuri on 2. Joten aiomme toistaa tämä prosessi uudelleen, Toista, kunnes swap laskuri on 0. Nollaa swap laskuri 0. Niin me nollata. 

Nyt näyttää jokaisen vierekkäisen parin. Se on kunnossa, 1 ja 2. 2 ja 3 ovat kunnossa. 3 ja 4 ovat kunnossa. Joten tässä vaiheessa, huomaa olemme valmiiksi katsomalla jokainen vierekkäisten, mutta swap laskuri on edelleen 0. 

Jos meillä ei ole vaihtaa kaikki elementit, sitten he on oltava kunnossa, mukaan nojalla tämän prosessin. Ja niin tehokkuus tapaisena, että me tietotekniikan tutkijoita rakastamme, on nyt voimme julistaa koko ryhmän täytyy järjestellä, koska emme täytyy vaihtaa mitään osia. Se on ihan kiva. 

Niin mitä pahimmassa tapauksessa skenaario kanssa kuplalajittelu? Pahimmassa tapauksessa matriisi on täysin päinvastaisessa järjestyksessä, ja niin meidän on kupla kunkin suurten elementtien kaikki tavalla koko jono. Ja me tehokkaasti on myös kupla kaikki pienet elementit takaisin koko matkan array, liian. Näin ollen jokainen n alkio on siirtää poikki kaikki muut n-elementtejä. Niin, että pahimmassa tapauksessa. Parhaassa tapauksessa skenaario kuitenkin, tämä on hieman erilainen valinta lajitella. Array on jo lajiteltu kun menemme sisään. Meillä ei tarvitse tehdä mitään swap ensimmäisellä omille. Joten saatamme täytyy katsoa klo vähemmän osia, eikö? Meillä ei tarvitse toistaa tätä käsitellä useita kertoja. 

Mitä tämä tarkoittaa? Niin mitä pahimmassa tapauksessa varten kuplalajittelu, ja mitä paras skenaario kuplalajittelu? Arvasit tämän? Pahimmassa tapauksessa joudut kerrata kaikissa n elementtiä n kertaa. Joten pahimmassa tapauksessa on n potenssiin. 

Jos matriisi on täysin lajiteltua kuitenkin, sinun vain täytyy katsoa jokaisen elementtien kerran. Ja jos swap laskuri on edelleen 0, voit sanoa tämän taulukon lajitellaan. Ja niin parhaassa tapauksessa, tämä on itse asiassa parempi kuin valinta sort-- se on omega n. 

Olen Doug Lloyd. Tämä on CS50.