>> [Zenelejátszási]
DOUG LLOYD: Rendben, buborékos rendezést egy algoritmus
segítségével rendezni egy sor elemet.
Vessünk egy pillantást, hogyan működik.
>> Tehát az alapötlet mögött buborékos rendezést ez.
Mi általában szeretnének feljebb értékes elemei általában a jobb,
és engedje értékes elemek általában balra, ahogy várnánk.
Szeretnénk, ha az alacsonyabb dolgokat, hogy a Az elején, és a magasabb dolgok
hogy a végén.
>> Hogyan tudjuk ezt megtenni?
Nos pszeudokód kódot, mondhatnánk, nézzük
állítsa a swap számláló nem nulla értéket.
Meglátjuk, hogy miért csináljuk, hogy egy másodperc.
És akkor ismételje meg a következő folyamatot, amíg a swap-számláló 0,
vagy amíg nem teszünk csereügyletek egyáltalán.
>> Állítsa vissza a swap-számláló 0, ha még nincs 0.
Akkor nézd meg minden szomszédos pár elemekkel.
Ha e két elem Nem azért, cserélni őket,
és adjunk hozzá 1 a swap számláló.
Ha még nem gondolkodik ezt, mielőtt képzelni,
észre, hogy ez fog mozogni az alacsonyabb értékes elemek balra
és a magasabb értékű elemek a jogot, hatékonyan teszi, amit akarunk csinálni,
ami mozog azoknak a csoportoknak Az elemek ilyen módon.
Nézzük elképzelni, hogy ez a nézhet a mi tömb
hogy mi használt teszt ki ezeket az algoritmusokat.
Van egy rendezetlen tömb újra itt, által jelzett összes elem
hogy a piros.
És tudom a swap-counter hogy egy nem nulla értéket.
Én önkényesen választotta negatív 1-- ez nem 0.
Szeretnénk megismételni ezt a folyamatot amíg a swap-számláló 0.
Ez az oka annak megadom a swap- számláló néhány nem nulla értéket,
mert egyébként az swap-számláló 0 lenne.
Akkor nem is kezdődik a folyamat az algoritmus.
Tehát ismét a lépéseket are-- állítsa vissza a swap számláló
0, akkor nézd meg minden szomszédos pár, és ha ők ki annak érdekében,
cserélni őket, és adjunk hozzá 1 a swap számláló.
Kezdjük ezt a folyamatot.
Tehát az első dolog, amit tennie, mi meg a swap-számlálóját 0,
és akkor kezdeni minden egyes szomszédos párja.
>> Tehát először kezdeni a 5 és 2.
Látjuk, hogy ezek közül rendelni, és így cserélni őket.
És mi adjunk hozzá 1 a swap számláló.
Tehát most mi swap-számláló értéke 1, 2, illetve 5 vannak kapcsolva.
Most ismételjük meg a folyamatot újra.
>> Nézzük a következő szomszédos pár, 5 és 1-- ők is elromlott,
így cserélni őket, és adjunk hozzá 1 a swap számláló.
Akkor nézzük 5 és 3.
Ők elromlott, így csere őket, és adjunk hozzá 1 a swap számláló.
Akkor nézzük az 5. és 6..
Ők annak érdekében, így valójában nem kell cserélni semmit ebben az időben.
Akkor nézd meg a 6. és a 4.
Ők is elromlott, így csere őket, és adjunk hozzá 1 a swap számláló.
>> Most észre, mi történt.
Már költözött 6 egészen a végéig.
Tehát a kiválasztási sorrend, ha már Látható, hogy a videót, amit tett,
Végül aztán a legkisebb eleme épület
A rendezett tömbben alapvetően balról jobbra, a legkisebbtől a legnagyobb.
Abban az esetben, buborékos rendezést, ha mi vagyunk ezt követően adott algoritmus,
vagyunk valójában lesz az épület A rendezett tömbben jobbról
balra, legnagyobb a legkisebb.
Mi már hatékonyan vezetünk 6, a legnagyobb értéke, egészen a végéig.
>> És így most már kijelentem hogy mely válogatni,
és a jövőben iterations-- megy át a tömb again--
nem kell figyelembe vennie a 6. többé.
Elég, ha csak úgy A rendezetlen elemek
ha keresünk szomszédos pár.
Szóval mi befejeztük az egyik áthaladnak buborékos rendezést.
Tehát most megyünk vissza a kérdésre, ismételjük, amíg a swap számláló 0.
Nos a swap counter 4, így fogunk
ismételgetni ezt a folyamatot újra.
>> Megyünk vissza a swap számláló 0, és nézd meg két szomszédos.
Szóval kezdjük a 2. és 1-- ők elromlott, így cserélni őket
és mi adjuk hozzá 1 a swap számláló.
A 2. és 3., ők érdekében.
Nem kell semmit tennie.
3 és 5 rendben vannak.
Nem kell semmit ott.
>> 5 és 4, ezek ki a rend, és ezért
kell cserélni őket, és adjunk hozzá 1 a swap számláló.
És most már átkerült az 5., A következő legnagyobb eleme,
hogy a végén a szelektálatlan rész.
Így már hívni, hogy része a rendezve rész.
>> Most már nézi a képernyőn, és valószínűleg meg tudja mondani,
akárcsak én, hogy a tömb rendezve most.
De nem tudjuk bizonyítani, hogy még.
Nincs garancia hogy ez válogatni.
De ez az, ahol a swap számláló fog jöhet számításba.
>> Így már elkészült egy menetben.
A swap-számláló 2.
Mi is így fogjuk megismételni ezt a folyamatot újra,
ismételjük, amíg a swap számláló 0.
Állítsa vissza a swap-számlálóját 0.
Szóval majd vissza azt.
>> Most nézd meg két szomszédos.
Ez annak érdekében, 1 és 2.
A 2. és 3. rendben vannak.
A 3. és 4. érdekében.
Tehát ezen a ponton, észre Elkészítettük néztem minden szomszédos pár,
de a swap-számláló még mindig 0.
>> Ha nem kell váltani Azon elemek, akkor
kell lennie annak érdekében, azáltal, értelmében ezt a folyamatot.
És így a hatásfok a fajta, hogy számítógépes szakemberek szeretik,
A most már kijelentem az egész tömbnek kell
válogatni, mert nem meg kell cserélni minden eleme.
Ez nagyon szép.
>> Szóval mi a legrosszabb esetben forgatókönyv buborékos rendezést?
A legrosszabb esetben a tömb teljesen fordított sorrendben,
és ezért kell minden buborék A nagy elemek minden
Az utat az egész tömböt.
És mi is hatékonyan kell buborék összes kis elemek vissza
végig az egész tömb is.
Tehát minden egyes n elem kell mozognia szerte az összes többi N elemekkel.
Szóval ez a legrosszabb forgatókönyv.
A legjobb esetben forgatókönyv bár ez
kissé eltér a kiválasztási sorrend.
A tömb már válogatni, mikor megyünk.
Nem kell, hogy bármilyen csereügyletek az első menetben.
Tehát lehet, hogy meg kell nézni A kevesebb elem, ugye?
Nem kell megismételni ezt ahol számos alkalommal több.
>> Szóval mit is jelent ez?
Szóval mi a legrosszabb forgatókönyv A buborékos rendezést, és mi
A legjobb esetben a buborékos rendezést?
Találta ki ezt?
A legrosszabb esetben, ha a közelítéseket minden az n elem n-szer.
Tehát a legrosszabb eset n faragva.
>> Ha a tömb tökéletesen szétválogatott mégis, akkor csak
meg kell nézni az egyes az elemek egyszer.
És ha a swap számláló még mindig 0, akkor lehet mondani, ez a tömb rendezve.
És így a legjobb esetben, ez sokkal jobb, mint kiválasztási
sort-- ez az omega n.
>> Én Doug Lloyd.
Ez CS50.