>> [MUZIKO Ludante]
DOUG LLOYD: Bone, do bobelo varo estas algoritmo
vi povas uzi por ordigi aro de elementoj.
Ni rigardu kiel ĝi funkcias.
>> Do la baza ideo malantaŭ bobelo varo estas tiu.
Ni ĝenerale deziras movi altaj valoraj elementoj ĝenerale al la dekstra,
kaj malaltigi valoraj elementoj ĝenerale maldekstren, kiel ni atendus.
Ni volas la malsupra aferojn esti ĉe la komenco, kaj la pli altaj aferoj
esti fine.
>> Kiel ni faru tion?
Nu en _pseudocode_ kodo, ni povus diri, ni
fiksi interŝanĝa vendotablo al ne-nula valoro.
Ni vidos kial ni faru tion en dua.
Kaj tiam ni ripetu la jenaj procezo ĝis la interŝanĝa vendotablo estas 0,
aŭ ĝis ni faru svopoj ajn.
>> Restarigi la interŝanĝa kontraŭas 0 se ĝi ne estas jam 0.
Tiam rigardi ĉiun apuda paro de elementoj.
Se tiuj du elementoj estas ne en ordo, interŝanĝi ilin,
kaj aldoni 1 al la vendotablo interŝanĝa.
Se vi pensas pri tiu antaŭ vi bildigi ĝin,
rimarki ke tiu movos malsupra valoraj elementoj maldekstren
kaj alta takso elementojn al la dekstra, efike fari kion ni volas fari,
kio estas movi tiuj grupoj de elementoj en tiu maniero.
Ni visualizar kiel ĉi povus rigardi uzante nia tabelo
ke ni kutimis testi el tiuj algoritmoj.
Ni havas unsorted tabelo tien; indikita de ĉiuj de la elementoj
estante en ruĝa.
Kaj mi turnis mian interŝanĝa vendotablo por nenula valoro.
Mi arbitre elektis negativa 1-- ĝi ne estas 0.
Ni volas ripeti tiun procezon ĝis la interŝanĝa vendotablo estas 0.
Tial mi starigis mian swap vendotablo al iu ne-nula valoro,
ĉar alie la interŝanĝa vendotablo estus 0.
Ni eĉ ne komenci la procezo de la algoritmo.
Do denove, la paŝoj are-- retrovu la interŝanĝa vendotablo
al 0, tiam rigardu ĉiun apuda paro, kaj se ili estas el ordo,
interŝanĝi ilin, kaj aldonu 1 al la interŝanĝa vendotablo.
Do ni komencu ĉi procezo.
Do la unua afero ni fari estas Ni starigu la interŝanĝa vendotablo al 0,
kaj poste ni komencas rigardanta ĉe ĉiu najbara paro.
>> Do ni unue komenci rigardi 5 kaj 2.
Ni vidas ke ili estas el ordigi kaj tiel ni interŝanĝi ilin.
Kaj ni aldonas 1 al la interŝanĝa vendotablo.
Do nun nia interŝanĝa vendotablo estas 1, kaj 2 kaj 5 estis interŝanĝita.
Nun ni ripetos la procezon denove.
>> Ni rigardas la sekva apuda paro, 5 kaj 1-- ili estas ankaŭ el ordo,
do ni interŝanĝi ilin kaj aldoni 1 por la interŝanĝa vendotablo.
Tiam ni rigardas 5 kaj 3.
Ili estas el ordo, Do ni interŝanĝu ili kaj ni aldonas 1 al la interŝanĝa vendotablo.
Tiam ni rigardas 5 kaj 6.
Ili estas en ordo, do ni ne vere bezonas interŝanĝi ion ĉi tempo.
Tiam ni rigardas 6 kaj 4.
Ili estas ankaŭ el ordo, Do ni interŝanĝu ili kaj ni aldonas 1 al la interŝanĝa vendotablo.
>> Nun rimarki kio okazis.
Ni translokiĝis 6 tutan vojon al la fino.
Do selektado speco, se vi havas vidis ke filmetoj, kion ni faris estis
ni finis kopiante la malgrandaj elementoj en konstruaĵo
la ordo tabelo esence el maldekstre dekstren, la plej malgranda al plej granda.
En la kazo de bobelo varon, se ni estas sekvante tiu aparta algoritmo,
Ni efektive tuj estos konstruado la ordo tabelo de dekstra
al maldekstra, granda ol plej malgranda.
Ni efike bobelis 6, La plej granda valoro, la tutan vojon al la fino.
>> Kaj tiel ni povas nun deklari ke kiu ordigataj
kaj en estonteco iterations-- irante tra la tabelo again--
ni ne devas konsideri 6 anymore.
Ni nur devas konsideri la unsorted elementoj
kiam ni rigardas najbaraj paroj.
Do ni finis unu trapasi bobelo varon.
Do nun ni reiros al la demando, ripeti ĝis la interŝanĝa vendotablo estas 0.
Nu la interŝanĝa vendotablo estas 4, do ni tuj
teni ripetante tiun procezon denove.
>> Ni tuj reagordi la interŝanĝa vendotablo al 0, kaj aspektas ĉe ĉiu najbara paro.
Do ni komencu per 2 kaj 1-- ili estas el ordo, Do ni interŝanĝu ilin
kaj ni aldonas 1 al la interŝanĝa vendotablo.
2 kaj 3, ili estas en ordo.
Ni ne bezonas fari ion.
3 kaj 5 estas en ordo.
Ni ne bezonas fari ion tie.
>> 5 kaj 4, ili estas ekstere de ordo, kaj tiel ni
bezonas interŝanĝi ilin kaj aldoni 1 por la interŝanĝa vendotablo.
Kaj nun ni movis 5, la sekva plej granda ero,
al la fino de la unsorted porcion.
Do ni povas nun nomas parto de la ordo parton.
>> Nun vi rigardas la ekrano kaj probable povas diri,
kiel mi povas, ke la tabelo estas ordo nun.
Sed ni ne povas pruvi ke ankoraŭ.
Ni ne havas garantion ke ĝi estas ordo.
Sed ĉi tiu estas kie la interŝanĝa vendotablo tuj veni en ludon.
>> Do ni kompletigis enirpermesilon.
La interŝanĝa vendotablo estas 2.
Do ni tuj ripetas tiu procezo denove,
ripeti ĝis la interŝanĝa vendotablo estas 0.
Restarigi la interŝanĝa vendotablo al 0.
Do ni reagordi ĝin.
>> Nun rigardu ĉiu najbara paro.
Tio en ordo, 1 kaj 2.
2 kaj 3 estas en ordo.
3 kaj 4 estas en ordo.
Do en ĉi tiu punkto, ni rimarkos kompletigita rigardante ĉiu apuda paro,
sed la interŝanĝa vendotablo estas ankoraŭ 0.
>> Se ni ne devas ŝanĝi ajna elementoj, tiam ili
devas esti en ordo, de virto de tiu procezo.
Kaj tial efikeco de varoj, ke ni komputikistoj ami,
Estas ni povas nun deklari la tuta tabelo devas
esti ordo, ĉar ni ne devi interŝanĝi ajnan elementoj.
Tio estas sufiĉe bela.
>> Do kio estas la plej malbona kazo scenaro kun bobelo varo?
En la plej malbona kazo la tabelo estas en tute inversa ordo,
kaj do ni devas bobelo ĉiu de la grandaj elementoj ĉiuj
la vojo trans la tabelo.
Kaj ni efike ankaŭ devas bobelo ĉiujn la malgrandaj elementoj reen
tutan vojon tra la vicojn, ankaŭ.
Do ĉiu el la n elementoj devas movi tra ĉiuj de la aliaj n elementoj.
Do jen la plej malbona kazo scenaron.
En la plej bona kazo scenaro tamen, tiu estas
iomete malsama de selektado varon.
La tabelo estas jam ordo kiam ni iros.
Ni ne devas fari ajnan svopoj sur la unuan enirpermesilon.
Do ni eble devus rigardi ĉe pli malmultaj elementoj, ĉu ne?
Ni ne devas ripeti tiun procesi plurajn fojojn super.
>> Do kion tio signifas?
Do kio estas la plej malbona kazo scenaro por bobelo varo, kaj kio estas
la plej bona kazo scenaro por bobelo varo?
Ĉu vi povas diveni tion?
En la plej malbona kazo vi devas persisti trans ĉiuj n elementoj n fojojn.
Do la plej malbona kazo estas n kvadratoj.
>> Se la tabelo estas perfekte ordo tamen, vi nur
devas rigardi ĉiun de la elementoj tuj.
Kaj se la interŝanĝa vendotablo estas ankoraŭ 0, vi povas diri ĉi tabelo estas ordigita.
Kaj tiel en la plej bona kazo, tiu estas efektive pli bona ol selektado
sort-- estas omega de n.
>> Mi Doug Lloyd.
Jen CS50.