[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.