>> [Muzikos grojimo]
Doug LLOYD: Gerai, taip burbulas rūšiuoti yra algoritmas
galite naudoti norėdami rūšiuoti iš elementų rinkinį.
Paimkime, kaip ji veikia išvaizdą.
>> Taigi pagrindinė idėja burbulas rūšiuoti tai.
Mes paprastai nori judėti didesnis vertinami elementai paprastai į dešinę
ir nuleiskite vertinami elementų, kuriais paprastai į kairę, kaip galima būtų tikėtis.
Mes norime, kad mažesnės dalykai turi būti ne pradžia, ir aukštesni dalykai
būti pabaigoje.
>> Kaip mes tai darome?
Na Pseudocode kodas, galima sakyti, tegul
nustatyti apsikeitimo skaitiklį į ne nulinės vertės.
Pamatysime, kodėl mes galime padaryti, kad per sekundę.
Ir tada mes pakartoti taip procesas, kol apsikeitimo skaitiklis yra 0,
arba tol, kol mes nedarome apsikeitimo ne visiems.
>> Atstatyti apsikeitimo skaitiklį į 0, jei tai ne jau 0.
Tada pažvelgti kas greta elementų pora.
Jei šie du elementai yra ne tam, apsikeitimo juos,
ir pridėti 1 iki apsikeitimo skaitiklis.
Jei jūs galvojate apie tai prieš jums vizualizuoti tai,
pastebėsite, kad tai bus perkelti mažesnis vertinami elementai į kairę
ir didesnis vertinami elementus į dešinę, efektyviai daryti tai, ką norime daryti,
kuris yra perkelti šias grupes iš elementų, tokiu būdu.
Leiskite įsivaizduoti, kaip tai gali atrodyti, naudodami mūsų masyvas
kad mes naudojamas testas iš šių algoritmų.
Čia mes turime nerūšiuotas masyvo vėl, visi iš elementų, nurodyta
yra raudona spalva.
Aš nukreipiau savo apsikeitimo skaitiklis prie nulio vertės.
Aš savavališkai pasirinko neigiamas 1-- tai ne 0.
Mes norime pakartoti šį procesą iki apsikeitimo skaitiklis yra 0.
Tai kodėl aš nustatyti savo apsikeitimo prieštarauja tam tikru ne nulinės vertės,
nes kitaip apsikeitimo skaitiklis būtų 0.
Mes net ne prasidės procesas algoritmą.
Taigi dar kartą, veiksmai are-- naujo apsikeitimo skaitiklis
0, tada pažvelgti į kiekvieną šalia pora, ir jei jie iš tam,
apsikeitimo juos ir pridėti 1 į apsikeitimo skaitiklis.
Taigi pradėkime šį procesą.
Taigi pirmas dalykas, mes darome, yra mes nustatome apsikeitimo skaitiklis 0,
ir tada mes pradėti ieškoti kiekvieno gretimo pora.
>> Taigi mes pirmą kartą pradėti ieškoti 5 ir 2.
Matome, kad jie yra iš užsisakyti ir todėl mes apsikeitimo juos.
Ir mes pridėti 1 iki apsikeitimo skaitiklis.
Taigi dabar mūsų apsikeitimo skaitiklis yra 1, ir 2 ir 5 buvo įjungtas.
Dabar mes vėl pakartokite šį procesą.
>> Pažvelgtume į kitą gretimos poros, 5 ir 1-- jie taip pat iš eilės,
todėl mes apsikeitimo juos ir pridėti 1 apsikeitimo skaitiklis.
Tada mes pažvelgti 5 ir 3.
Jie iš eilės, todėl mes apsikeitimo juos ir mes pridėsime 1 iki apsikeitimo skaitiklis.
Tada mes pažvelgti 5 ir 6 d.
Jie tam, kad mes ne iš tikrųjų reikia sukeisti nieko šiuo metu.
Tada mes pažvelgti 6 ir 4.
Jie taip pat iš eilės, todėl mes apsikeitimo juos ir mes pridėsime 1 iki apsikeitimo skaitiklis.
>> Dabar pastebėti tai, kas atsitiko.
Mes persikėlė 6 visą kelią iki galo.
Taigi atrankos rūšiuoti, jei jūs matyti, kad vaizdo, ką mes padarėme, buvo
mes galų gale perstumiant Mažiausi elementai pastato
surūšiuoti masyvo ir iš esmės kairės į dešinę, mažiausio iki didžiausių.
Atsižvelgiant į burbulas rūšiuoti atveju, jei mes po šio konkretaus algoritmo,
mes iš tikrųjų ketiname būti pastato surūšiuoti masyvas iš dešinės
į kairę, didžiausiojo iki mažiausiojo.
Mes efektyviai burbuliukais 6 d didžiausia vertė, visą kelią iki galo.
>> Ir taip dabar mes galime paskelbti kad tai būtų rūšiuojamos,
ir ateityje iterations-- išgyvena masyvo again--
mes neturime apsvarstyti 6 nebėra.
Mes turime tik mano kad nerūšiuotos elementai
kai mes ieškome gretimų porų.
Taigi, mes turime baigė vieną pro burbulas rūšiuoti.
Taigi dabar mes einame atgal į klausimą, kartokite tol, kol apsikeitimo skaitiklis yra 0.
Na apsikeitimo skaitliukas yra 4, todėl mes ketiname
išlaikyti vėl kartoti šį procesą.
>> Mes ketiname iš naujo apsikeitimo skaitiklis 0, ir ieškoti kiekvienos gretimos poros.
Taigi, mes pradėti su 2 ir 1-- jie iš eilės, todėl mes apsikeitimo juos
ir mes pridėsime 1 iki apsikeitimo skaitiklis.
2 ir 3, jie tam.
Mums nereikia nieko daryti.
3 ir 5 yra tam, kad.
Mums nereikia nieko ten daryti.
>> 5 ir 4, jie yra iš iš eilės, ir todėl mes
reikia sukeisti juos ir pridėti 1 apsikeitimo skaitiklis.
Ir dabar mes persikėlė 5, Kitas didžiausias elementas,
į nerūšiuotųomis porcija pabaigoje.
Taigi dabar mes galime skambinti, kad dalis surūšiuoti porcijoje.
>> Dabar jūs ieškote ne ekranas ir tikriausiai galite pasakyti,
kaip aš galiu, kad masyvo yra rūšiuojami dabar.
Bet mes negalime įrodyti, kad dar.
Neturime garantiją kad jis rūšiuojami.
Bet tai kur apsikeitimo skaitliukas ketina ateiti į žaidimą.
>> Taigi mes baigė perdavimo.
Apsikeitimo skaitiklis yra 2.
Taigi mes ketiname pakartoti vėl šis procesas,
kartokite tol, kol apsikeitimo skaitiklis yra 0.
Atstatyti apsikeitimo skaitiklis 0.
Taigi mes jį atstatyti.
>> Dabar pažvelgti į kiekvieną greta pora.
Štai, kad 1 ir 2.
2 ir 3 yra tam, kad.
3 ir 4, yra tam, kad.
Taigi šiuo metu, pastebėsite, mes baigtas žiūri kiekvieną greta pora,
bet apsikeitimo skaitiklis yra vis dar 0.
>> Jei mes neturime pereiti bet elementai, tada jie
turi būti tam, kurį dorybė šio proceso dalis.
Ir taip AN rūšių efektyvumas, kad mes kompiuterių mokslininkai myliu,
yra dabar galime paskelbti visas masyvas turi
būti rūšiuojamos, nes mes ne turi apsikeitimo jokių elementų.
Tai gana gražus.
>> Taigi, kas blogiausiu atveju scenarijus su burbulas rūšiuoti?
Blogiausiu atveju masyvas yra į visiškai atvirkštine tvarka,
ir todėl mes turime kiekvienas burbulas didžiųjų elementų visi
būdas visoje masyvo.
Ir mes iš tikrųjų taip pat turi burbuliukų visi mažų elementų atgal
visą kelią visoje masyvo, taip pat.
Taigi, kiekvienas iš n elementų turi judėti visoje visų kitų n elementų.
Taigi, kad blogiausiu atveju.
Geriausiu atveju scenarijus, nors tai
šiek tiek skiriasi nuo atrankos rūšiuoti.
Masyvas yra jau rūšiuojamos, kai mes einame.
Neturime padaryti bet apsikeitimo pirmame praeiti.
Taigi, mes galime pažvelgti ne mažiau elementų, tiesa?
Neturime pakartoti apdoroti keletą kartų per.
>> Taigi, ką tai reiškia?
Taigi, kas yra blogiausias scenarijus Kramtomoji rūšiuoti, ir kas
Geriausiu atveju scenarijus burbulas rūšiuoti?
Ar galite atspėti, tai?
Blogiausiu atveju jūs turite pakartoti visose n elementų n kartų.
Taigi blogiausiu atveju yra N kvadratu.
>> Jei masyvas yra puikiai Rūšiuoti nors, jūs tik
pažvelgti į kiekvieną Vieną kartą elementų.
Ir jei apsikeitimo skaitiklis yra vis dar 0, galite pasakyti, kad tai masyvas surūšiuotas.
Ir taip geriausiu atveju, tai yra tikrai geriau nei atrankos
sort-- tai omega n.
>> Aš Doug Lloyd.
Tai CS50.