[Powered by Google Translate] [BUBBLE RŪŠIUOTI]
[JACKSON STEINKAMP Harvardo universiteto]
[Tai CS50. CS50TV]
Burbulas Rūšiuoti rūšiavimo algoritmą pavyzdys -
kad yra elementų rinkinys rūšiavimo tvarka
didėjimo arba mažėjimo tvarka.
Pavyzdžiui, jei norite rūšiuoti masyvo, sudarytas iš skaičių
[3, 5, 2, 9], teisingas įgyvendinimas Bubble Rūšiuoti sugrįš
surūšiuoti masyvas [2, 3, 5, 9] didėjimo tvarka.
Dabar, aš paaiškinti pseudocode, kaip algoritmas veikia.
>> Tarkime, mes rūšiavimo 5 sveikųjų skaičių sąrašą 3, 2, 9, 6, 5.
Algoritmas prasideda žiūri pirmaisiais dviem elementais, 3 ir 2,
ir tikrinti, ar jie iš siekiant tarpusavyje susijusius.
Jie - 3 yra didesnis kaip 2.
Būti didėjančia tvarka, jie turėtų būti atvirkščiai.
Taigi, mes apsikeitimo juos.
Dabar sąrašas atrodo panašus į šį: [2, 3, 9, 6, 5].
>> Be to, mes pažvelgti į antros ir trečios dalių, 3 ir 9.
Jie teisinga tvarka, viena kitos atžvilgiu.
Tai reiškia, kad 3 yra mažesnis kaip 9, algoritmas nėra apsikeitimo juos.
Be to, mes tikimės, 9 ir 6. Jie ne iš eilės.
>> Taigi, mes turime apsikeitimo juos, nes 9 yra didesnis kaip 6.
Galiausiai, mes pažvelgti į pastaruosius du sveikieji skaičiai, 9 ir 5.
Jie ne iš eilės, todėl jie turi būti sukeistas.
Po pirmojo visiškai patenka per sąrašą,
atrodo panašus į šį: [2, 3, 6, 5, 9].
Nėra blogai. Tai beveik surūšiuoti.
Bet mes turime paleisti per sąrašą, vėl jį gauti visiškai rūšiuojami.
Du yra mažesnis nei 3, todėl mes negalime apsikeitimo juos.
>> Trys yra mažiau nei 6, todėl mes negalime apsikeitimo juos.
Šeši yra didesnis nei 5. Mes pavertė.
Six "yra mažesnis kaip 9. Mes neturime apsikeitimo.
Po antrojo skrendant per, atrodo taip: [2, 3, 5, 6, 9]. Tobula.
Dabar galime rašyti į pseudocode.
Iš esmės, kiekvieno sąrašo elemento, mes turime pažvelgti į ją
elementas tiesiogiai į savo teisę.
Jei jie yra ne iš eilės lyginant su kiekviena kita - tai yra, jei kairėje elementas
yra didesnis, nei dešinėje pusėje - turėtume sukeisti du elementus.
>> Mes tai darome, kiekvienas sąrašo elementas, ir mes padarėme vieną pro.
Dabar mes tiesiog daryti pass-through pakankamai kartų, siekiant užtikrinti, sąrašą
yra visiškai ir tinkamai surūšiuoti.
Bet kiek kartų mes turime praeiti pro sąraše
garantuoti, kad mes padarėme?
Na, blogiausiu atveju scenarijus, jei mes turime visiškai atgal sąrašą.
Tada ji užima Pass-throughs lygus skaičius
elementų n-1.
Jei tai nėra prasmės intuityviai, manau, paprastu atveju - sąrašas [2, 1].
>> Ketina imtis 1 pass-through, rūšiuoti teisingai.
[3, 2, 1] - blogiausiu atveju yra tai, kad su 3 elementus surūšiuoti atgal
ji ketina imtis 2 iteracijų rūšiuoti.
Po vienos iteracijos, [2, 1, 3].
Antra duoda surūšiuoti masyvas [1, 2, 3]
Taigi jūs žinote, jūs niekada neturite eiti per masyvo, apskritai,
daugiau nei n-1 kartų, kur n - masyvo elementų skaičius.
Tai vadinama burbulas Rūšiuoti nes didžiausi elementai turi tendenciją "burbuliukų"
gana greitai į dešinę.
Tiesą sakant, šis algoritmas turi labai įdomią elgesį.
>> Po m iteracijų per visą masyvą,
dešinė M elementai garantuoja
būti suskirstyti į jų teisingą vietą.
Jei norite pamatyti šį sau,
mes galime pabandyti jį visiškai atgalinio sąrašą [9, 6, 5, 3, 2].
Po vienu važiavimu per visą sąrašą,
[Rašymo garso]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
yra savo vietoje dešinė elementas 9.
Po antrojo pass-through, 6 turės "burbuliukų-up"
2. dešinė vieta.
Dešinėje - 6 ir 9 - šie du elementai bus jų teisingas vietas
po pirmųjų dviejų Pass-throughs.
>> Taigi, kaip mes galime naudoti šį optimizuoti algoritmą?
Na, po vieną iteracijoje masyvo
mes ne iš tikrųjų reikia patikrinti dešinė elementas
nes mes žinome, tai rūšiuojamos.
Po dviejų iteracijų, mes žinome, tikrai dešinė du elementai yra.
Taigi, apskritai, po k iteracijų per visą spektrą,
tikrinti paskutinius k elementai yra nereikalingas, nes mes žinome,
jie jau į reikiamą vietą.
>> Taigi, jei jūs rūšiuojant n elementų masyvą,
pirmajam iteracijos procesui - ty jūs turite rūšiuoti visi elementai - pirmasis N-0.
Dėl antrosios iteracijos, jūs turite pažvelgti į visus elementus, tačiau paskutinį -
n-1.
Kitas optimizavimas gali būti patikrinti, ar sąrašas jau yra surūšiuoti
po kiekvienos iteracijos.
Jei jis jau rūšiuojamos, mums nereikia, kad daugiau iteracijų
per sąrašą.
Kaip mes galime tai padaryti?
Na, jei mes neturime jokių pass-through sąrašo apsikeitimo sandorius,
dabar jau aišku, kad šis sąrašas jau buvo surūšiuoti, nes mes neturėjome apsikeitimo nieko.
Taigi mes tikrai neturite rūšiuoti vėl.
>> Gal galėtumėte inicijuoti vėliavos kintamasis vadinamas "nėra rūšiuojamos"
false ir pakeiskite ją "true", jei jūs turite apsikeitimo jokių įrodymų dėl
vienas iš pasikartojančių per masyvo.
Ar panašiai, kad skaitiklis suskaičiuoti, kiek apsikeitimo sandoriai jums padaryti
bet kuriuo iteracijos.
Yra iteracijos pabaigoje, jei tu negali apsikeitimo elementų,
žinote, sąrašas jau yra rūšiuojami ir baigsite.
Burbulas Rūšiuoti, kaip ir kiti rūšiavimo algoritmų, gali būti
nežymiai dirbti bet kokius elementus, kurie turi užsakymo metodą.
>> Tai reiškia, kad du elementai jūs turite būdas pasakyti, jei pirmasis
yra didesnis nei yra lygi arba mažesnė už antrąją.
Pavyzdžiui, galite rūšiuoti abėcėlės raidėmis, sakydamas
kad a <b, b <c ir tt
Arba jums gali rūšiuoti savaitės dienomis, sekmadienis yra mažiau nei pirmadienis
kuris yra mažesnis nei antradienis.
>> Burbulas Rūšiuoti jokiu būdu nėra labai efektyviai arba greito rūšiavimo algoritmą.
Blogiausiu atveju Runtime Didelės O n ²
nes jūs turite padaryti n iteracijų per sąrašo
tikrina visus n elementų, kiekvienas pass-through, nxn = n ².
Šios įsibėgėjimo laikas reiškia, kad kaip elementų jūs rūšiavimo didėja,
vykdymo metu padidina kvadratin.
>> Tačiau, jei efektyvumas nėra pagrindinis rūpestis savo programą
arba jei jūs tik nedaug elementų rūšiavimas,
galite rasti burbulas Rūšiuoti naudinga, nes
tai vienas iš paprasčiausių rūšiavimo algoritmų suprasti
ir kodas.
Jis taip pat yra puikus būdas įgyti patirties su vertimu teorinis
algoritmas faktinės veikiančios kodu.
Gerai, kad burbulas Rūšiuoti Jums. Thanks for watching.
CS50.TV