>> [Predvaja glasba]
Doug LLOYD: V redu, tako da bubble nekako je algoritem
lahko uporabite za razvrščanje niz elementov.
Oglejmo si, kako to deluje.
>> Torej osnovna ideja bubble nekako gre.
Smo na splošno želijo premakniti višje cenjene elementi običajno na desni,
in nižje vrednotijo ​​elemente splošno na levi, kot bi pričakovali.
Želimo nižje stvari, da se na začetek, in višje stvari
da je na koncu.
>> Kako to storiti?
No, v psevdokoda kodo, lahko bi rekli, Dovolite
nastaviti izmenjalno nasprotju z ne-ničelno vrednost.
Bomo videli, zakaj delamo to, da je v sekundi.
In potem smo ponovili naslednji Proces dokler swap števec 0,
ali dokler ne naredimo nobene zamenjave sploh.
>> Reset swap nasprotju z 0, če to ni že 0.
Potem poglej vse sosednji par elementov.
Če sta ta dva elementa ni v redu, jih zamenjajte,
in dodamo 1 do zamenjave števca.
Če razmišljate o tem to preden jo vizualizirati,
opazili, da se bo to premakniti nižje vrednotene elementi na levi
in višje vrednotijo ​​elemente v desno, dejansko to, kar želimo narediti,
ki se premikajo tiste skupine elementov v ta način.
Oglejmo vizualizirati, kako to lahko poiščete z uporabo našega niz
ki smo ga uporabili za testiranje od teh algoritmov.
Zopet smo imeli neurejen paleto tukaj, z vseh elementov navedeno
da je v rdeči barvi.
In jaz nastavim swap števec na neničelno vrednost.
Sem samovoljno odločil, negativna 1-- to ni 0.
Želimo, da ponovite ta postopek do zamenjave števca je 0.
To je razlog, zakaj sem iz moje swap v nasprotju z nekaterimi ne-ničelno vrednost,
ker v nasprotnem primeru swap Števec bi bilo 0.
Mi ne bi niti zajadrati v Postopek algoritma.
Torej še enkrat, koraki are-- reset swap števec
0, potem poglej na vsak sosednji par, in če oni v okvari,
swap njih, in dodamo 1 do zamenjave števca.
Torej začnimo ta proces.
Torej prva stvar, ki mi je smo postavili swap števec na 0,
in potem smo začeli iskati pri vsakim sosednjim parom.
>> Tako smo najprej začeli iskati na 5 in 2.
Vidimo, da so iz naročite in tako smo jih zamenjali.
In smo dodali 1 do zamenjave števca.
Torej, zdaj je naša swap števec je 1, in 2 in 5 so bili zamenjan.
Zdaj smo spet ponoviti postopek.
>> Gledamo na naslednji sosednji par, 5 in 1-- oni tudi v okvari,
zato smo jih zamenjali in dodajte 1 do zamenjave števca.
Potem gledamo na 5 in 3.
So v okvari, zato smo zamenjali jih in dodamo 1 do zamenjave števca.
Potem gledamo na 5 in 6.
Oni so v redu, tako da ne bomo dejansko morali zamenjati ničesar ta čas.
Potem gledamo na 6 in 4.
Oni so tudi v okvari, zato smo zamenjali jih in dodamo 1 do zamenjave števca.
>> Zdaj opazili, kaj se je zgodilo.
Mi smo se preselili 6 vse do konca.
Torej, v izbirnem vrste, če ste razvidno, da je video, kar smo naredili je bilo
smo končali premikanje najmanjši elementi v stavbi
urejen matrika predvsem iz od leve proti desni, najmanjše do največje.
Pri mehurčkov vrste, če smo po tem algoritmu,
smo dejansko dogaja, da se gradi urejen matrika z desne
levo, največjih do najmanjših.
Smo uspešno mehurčkih 6, na Največja vrednost, vse do konca.
>> In tako smo zdaj lahko razglasi da je ta razporejene,
in v prihodnosti iterations-- gredo skozi paleto again--
nimamo razmisliti 6 anymore.
Imamo le, da razmisli nerazvrščenih elementi
ko smo iskali na sosednjih parov.
Tako smo končali eno skozi mehurček vrste.
Torej, zdaj gremo nazaj k vprašanju, ponovite, dokler swap števec je 0.
No swap števec je 4, zato bomo
da ponovno ponavljanjem postopka.
>> Bomo ponastaviti swap števec 0 in poglej vsakim sosednjim parom.
Tako smo začeli z 2 in 1-- oni v okvari, zato smo jih zamenjali
in dodamo 1 do zamenjave števca.
2 in 3, oni so v redu.
Mi ni treba storiti ničesar.
3 in 5 so v redu.
Mi ni treba storiti ničesar tam.
>> 5 in 4, so iz reda, in zato smo
potrebujejo, da jih swap in dodajte 1 do zamenjave števca.
In zdaj smo se preselili 5, Naslednji največji element,
na koncu nesortiranih odseka.
Tako bomo lahko zdaj pokličete, da del razvrščeni odseka.
>> Zdaj si pogledamo Zaslon in verjetno lahko povem,
kot lahko sem, da matriki je razvrščen zdaj.
Vendar še ne moremo dokazati, da.
Nimamo garancijo da je to urejeno.
Toda to je, če swap Števec se dogaja, da pridejo v poštev.
>> Tako smo zaključili sredino.
Swap števec je 2.
Torej bomo ponovili spet ta proces,
ponovite, dokler swap števec je 0.
Reset izmenjalno števec na 0.
Torej ga bomo ponastaviti.
>> Zdaj pa poglej vsakim sosednjim parom.
To je v redu, 1 in 2.
2 in 3 so v redu.
3 in 4 so v redu.
Torej, na tej točki, opazili smo zaključili gledaš vsak sosednji par,
vendar swap števec je še vedno 0.
>> Če ne bomo imeli, da preklopite vsak element, potem
mora biti v vrstnem redu, ki ga odlika tega procesa.
In tako izkoristek z menoj, da smo računalniški znanstveniki radi,
se bomo sedaj lahko razglasi celotna matrika mošt
treba sortirati, ker nismo storili morali zamenjati nobenih elementov.
To je zelo lepo.
>> Torej, kaj je v najslabšem primeru Scenarij z mehurček vrste?
V najslabšem primeru je matrika je v popolnoma obratnem vrstnem redu,
in zato moramo mehurček vsak velikih elementov vsi
pot čez polja.
In smo dejansko imeli tudi mehurček vse majhnih elementov nazaj
vso pot čez polja, preveč.
Torej je vsak izmed n elementov mora premakniti čez vse druge n elementov.
Tako, da je najslabši možni scenarij.
V najboljšem primeru scenarij, čeprav je to
nekoliko razlikujejo od izbora vrste.
Matrika je že razporejene, ko gremo v.
Nimamo, da bi katerikoli Zamenjave na prvo priložnost.
Tako bomo morda morali pogledati na manj elementov, kajne?
Nimamo ponoviti to obdelati večkrat konec.
>> Torej, kaj to pomeni?
Torej, kaj je najslabši možni scenarij za mehurček vrste, in kaj je
najboljši scenarij za bubble vrste?
Ali ste ugibati to?
V najslabšem primeru boste morali ponoviti vseh elementov N-krat.
Torej je v najslabšem primeru n kvadrat.
>> Če array je popolnoma sortirani, čeprav, samo vi
morali gledati na vsak elementov enkrat.
In če je swap števec je še vedno 0, lahko rečem je to matrika je razvrščen.
In tako v najboljšem primeru pa je to dejansko boljši od izbora
sort-- je omega n.
>> Sem Doug Lloyd.
To je CS50.