>> [Muzika]
DOUG Lloyd: Të gjithë të drejtë, kështu që flluskë lloj është një algoritëm
ju mund të përdorni për të zgjidhur një sërë elementesh.
Le të marrin një sy se si funksionon.
>> Pra, ideja themelore prapa flluskë lloj është kjo.
Ne në përgjithësi duan të lëvizin të lartë elemente me vlerë në përgjithësi në të djathtë,
dhe të ulët elemente me vlerë në përgjithësi në të majtë, ndërsa ne do të presim.
Ne duam që gjërat më të ulëta të jenë në fillimi, dhe gjërat më të larta
që të jetë në fund.
>> Si e bëjmë këtë?
Edhe në kodin e pseudokod, ne mund të themi, le të
vendosur një kundër swap në një vlerë jo-zero.
Ne do të shohim se pse ne bëjmë atë në një të dytë.
Dhe pastaj ne të përsëritur në vijim Procesi deri swap counter është 0,
ose derisa ne kemi bërë asnjë këmbime në të gjitha.
>> Reset counter swap për 0 në qoftë se ajo nuk është tashmë 0.
Pastaj të shohim në çdo palë ngjitur e elementeve.
Nëse këto dy elemente janë jo në mënyrë, të bie në ujdi tyre,
dhe shtoni 1 me swap banak.
Nëse jeni duke menduar në lidhje me kjo para se ju kujtoj atë,
vini re se kjo do të lëvizë më të ulët elemente me vlerë në të majtë
dhe elementët në të djathtë vlerë të lartë, në mënyrë efektive duke bërë atë që ne duam të bëjmë,
i cili është të lëvizë ato grupe e elementeve në këtë mënyrë.
Le të parashikoj se si kjo mund të duket përdorur array tonë
që kemi përdorur për të testuar nga këto algoritme.
Ne kemi një rrjet Unsorted këtu përsëri, treguar nga të gjithë elementët
duke qenë në të kuqe.
Dhe kam vendosur counter time swap në një vlerë jozero.
Unë zgjodha në mënyrë arbitrare negativ 1-- kjo nuk është 0.
Ne duam të përsërisim këtë proces derisa shkëmbimit banak është 0.
Kjo është arsyeja pse kam vendosur swap tim në kundërshtim me disa vlera jo-zero,
sepse përndryshe shkëmbim counter do të jetë 0.
Ne nuk do të fillojë edhe Procesi i algoritmi.
Pra, përsëri, hapat are-- reset swap counter
0, pastaj të shohim në çdo ngjitur palë, dhe nëse ata janë jashtë funksionit,
bie në ujdi tyre, dhe të shtoni 1 të swap banak.
Pra, le të fillojmë këtë proces.
Pra, gjëja e parë që bëni është të ne kemi vendosur swap counter në 0,
dhe pastaj ne fillojmë të shikojmë në çdo çift ngjitur.
>> Pra, ne së pari të fillojmë të shikojmë në 5 dhe 2.
Ne shohim se ata janë jashtë rendit dhe kështu që ne bie në ujdi tyre.
Dhe ne shtoni 1 me swap banak.
Kështu që tani shkëmbim counter tonë është 1, dhe 2 dhe 5 kanë qenë të ndezur.
Tani ne përsëris procesin përsëri.
>> Ne shikojmë në palë tjetër ngjitur, 5 dhe 1-- ata janë edhe jashtë funksionit,
kështu që ne bie në ujdi tyre dhe shtoni 1 në swap banak.
Atëherë ne shikojmë në 5 dhe 3.
Ata janë jashtë funksionit, kështu që ne të bie në ujdi ata dhe ne shtoni 1 me swap banak.
Atëherë ne shikojmë në 5 dhe 6.
Ata janë në rregull, kështu që ne nuk mund të vërtetë duhet të bie në ujdi asgjë këtë herë.
Atëherë ne shikojmë në 6 dhe 4.
Ata janë gjithashtu jashtë funksionit, kështu që ne të bie në ujdi ata dhe ne shtoni 1 me swap banak.
>> Tani vini re se çfarë ka ndodhur.
Ne kemi lëvizur 6 gjithë rrugës deri në fund.
Pra, në përzgjedhjes lloj, në qoftë se ju keni shihet se video, ajo që ne e bëmë ishte
ne përfundoi duke lëvizur Elementet më të vogla në ndërtesë
array renditura në thelb nga majta në të djathtë, më të vogël për të më e madhe.
Në rastin e flluskë lloji, në qoftë se ne jemi pas këtij algoritmi të veçantë,
ne jemi të vërtetë do të jetë ndërtimi array renditura nga e djathta
në të majtë, më i madh për të vogël.
Ne kemi bubbled efektive 6, vlera më e madhe, gjatë gjithë rrugës deri në fund.
>> Dhe kështu që ne tani mund të deklarojë se kjo është e renditura,
dhe në të ardhmen iterations-- shkuar nëpër rrjet again--
ne nuk duhet të marrin në konsideratë 6 më.
Ne vetëm duhet të marrin në konsideratë elementet Unsorted
kur ne jemi duke kërkuar në çifte ngjitur.
Pra, ne kemi përfunduar një kalojnë nëpër flluskë lloj.
Deri tani ne kthehemi në pyetjen: përsëris deri swap counter është 0.
Well swap counter është 4, kështu që ne jemi duke shkuar
për ta mbajtur përsëritur këtë proces përsëri.
>> Ne jemi duke shkuar për të rivendosur swap counter në 0, dhe të kërkoni në çdo palë ngjitur.
Pra, ne fillojmë me 2 dhe 1-- ata janë jashtë funksionit, kështu që ne të bie në ujdi tyre
dhe ne shtoni 1 me swap banak.
2 dhe 3, ata janë në rregull.
Ne nuk kemi nevojë të bëni asgjë.
3 dhe 5 janë në rregull.
Ne nuk kemi nevojë të bëjë asgjë atje.
>> 5 dhe 4, ata janë jashtë e rendit, dhe kështu që ne
duhet të bie në ujdi tyre dhe shtoni 1 në swap banak.
Dhe tani ne kemi lëvizur 5, elementi tjetër më i madh,
në fund të pjesës pandara.
Pra, ne tani mund të telefononi atë një pjesë e pjesës së renditura.
>> Tani ju jeni duke kërkuar në ekran dhe ndoshta mund të them,
si mund unë, se array është e renditura tani.
Por ne nuk mund të provojë se ende.
Ne nuk kemi një garanci se është e renditura.
Por, ky është vendi ku swap counter do të hyjë në lojë.
>> Pra, ne kemi përfunduar një abone.
Swap counter është 2.
Pra, ne jemi duke shkuar për të përsëritur ky proces përsëri,
përsëris deri swap counter është 0.
Reset swap counter në 0.
Pra, ne do të rivendosur atë.
>> Tani shikoni në çdo palë ngjitur.
Kjo është në rregull, 1 dhe 2.
2 dhe 3, janë në mënyrë të.
3 dhe 4 janë në mënyrë të.
Pra, në këtë pikë, vini re ne kemi përfunduar duke kërkuar në çdo palë ngjitur,
por swap counter është ende 0.
>> Në qoftë se ne nuk kemi për të kaluar Çdo elemente, atëherë ata
duhet të jetë në rregull, nga virtyt i këtij procesi.
Dhe kështu një efikasitet në terezi, se shkencëtarët kompjuterike ne dashuri,
është ne tani mund të deklarojë të gjithë grup duhet
të ndahen, sepse ne nuk e bëmë duhet të bie në ujdi asnjë element.
Kjo është shumë e bukur.
>> Pra, çfarë është rasti më i keq Skenari me flluskë lloj?
Në rastin më të keq array është në mënyrë krejtësisht të kundërt,
dhe kështu që ne duhet të flluskë çdo e elementeve të mëdha të gjithë
rruga nëpër rrjet.
Dhe ne në mënyrë efektive gjithashtu duhet të flluskë të gjitha elementet të vogla mbrapa
të gjithë rrugën nëpër rrjet, too.
Kështu që secili prej elementeve n ka për të lëvizur nëpër të gjitha elementet e tjera n.
Pra, kjo është skenari më i keq.
Në rastin më të mirë skenar edhe pse, kjo është
paksa e ndryshme nga përzgjedhjes lloji.
Array është tashmë renditura kur të shkojmë në.
Ne nuk duhet të bëjë ndonjë këmbime në kalimin e parë.
Pra, ne mund të duhet të shikojmë në më pak elemente, e drejtë?
Ne nuk kemi për të përsëritur këtë procesin disa herë gjatë.
>> Pra, çfarë do të thotë kjo?
Pra, çfarë është skenari më i keq për flluskë lloj, dhe çfarë është
skenari më i mirë për flluskë lloj?
A ju me mend kjo?
Në rastin më të keq se ju keni për të iterate në të gjitha elementet e n n herë.
Pra, rasti më i keq është katror n.
>> Nëse array është krejtësisht renditura edhe pse, ju vetëm
duhet të shikoni në çdo e elementeve të njëjtën kohë.
Dhe në qoftë se swap counter është ende 0, ju mund të them këtë grup është e renditura.
Dhe kështu në rastin më të mirë, kjo është në fakt më mirë se përzgjedhja
sort-- është omega e n.
>> Unë jam Doug Lloyd.
Kjo është CS50.