[Powered by Google Translate] [BUBBLE RENDEZÉS] [JACKSON Steinkamp Harvard Egyetem] [EZ CS50. CS50TV] Bubble rendezése egy példa a rendezési algoritmus - azaz egy eljárást rendezéséhez egy sor Elemek növekvő vagy csökkenő sorrendben. Például, ha akart rendezni egy tömb, ami a számok [3, 5, 2, 9], a helyes végrehajtása Bubble osztályozása visszatér a rendezett tömbben [2, 3, 5, 9], növekvő sorrendben. Most fogom elmagyarázni, hogyan pszeudokód az algoritmus működik. 

Tegyük fel, hogy mi válogatás egy listát az 5 egészek - 3, 2, 9, 6, és 5. Az algoritmus indul nézi most az első két elem, 3 és 2, és ellenőrzés, ha ők out of order egymáshoz képest. Ezek - 3 2-nél nagyobb. Ahhoz, hogy növekvő sorrendben kell lenniük a másik fordítva. Szóval, mi cserélni őket. Most a jegyzék néz ki: [2, 3, 9, 6, 5]. 

Ezután nézzük meg a második és a harmadik elem, 3 és 9. Ők a megfelelő sorrendben egymáshoz képest. Azaz, a 3. kevesebb, mint 9, így az algoritmus nem cserélni őket. Ezután nézzük a 9 és 6. Ők elromlott. 

Szóval, meg kell cserélni őket, mert 9 nagyobb, mint 6. Végül nézzük meg az utolsó két egész, 9 és 5. Ők meg a rend, ezért kell őket cserélni. Miután az első teljes áthaladnak a listán, így néz ki: [2, 3, 6, 5, 9]. Nem rossz. Már majdnem rendezve. De kell, hogy végig a listát újra a teljesen rendezve. Két kisebb, mint 3, így nem cserélni őket. 

Három a kisebb, mint 6, így nem cserélni őket. Hat több mint 5. Mi cserélték. Hat nem kevesebb mint 9. Nem cserélni. Miután a második lépésben át, úgy néz ki: [2, 3, 5, 6, 9]. Tökéletes. Most pedig írd azt pszeudokód. Alapvetően minden egyes elem a listán, meg kell nézni, hogy és az elem közvetlenül annak jobbra. Ha ők meghibásodott egymásnak megfelelően - azaz, ha a bal oldali elem nagyobb, mint az egyik a jobb - meg kell cserélni a két eleme van. 

Tesszük ezt minden egyes eleme a listáról, és tettünk egy menetben keresztül. Most már csak meg kell csinálni a pass-through elégszer, hogy biztosítsák a lista teljesen, megfelelően rendezve. De hányszor kell még át a listát garantálja, hogy készen vagyunk? Nos, a legrosszabb esetben is, ha egy teljesen hátra listát. Akkor tart számos át-átvezetéseket számával megegyező elemek n-1. Ha ez nincs értelme ösztönösen, gondolom, egy egyszerű ügy - a lista [2, 1]. 

Ez fog tartani az 1 pass-through rendezni helyesen. [3, 2, 1] - A legrosszabb eset az, hogy a 3 elem sorrendje hátrafelé, ez fog tartani 2 ismétléseket a rendezéshez. Miután egy iteráció, ez [2, 1, 3]. A második hozamok a rendezett tömbben [1, 2, 3]. Szóval, tudod, soha nem kell, hogy menjen át a tömb, általában több, mint n-1-szer, ahol n az elemek száma a tömbben. Úgy hívják Bubble rendezése, mert a legnagyobb elemek hajlamosak a "buborék-up" jobbra elég gyorsan. Valójában ez az algoritmus nagyon érdekes viselkedést. 

Miután m iteráció az egész tömb, A jobb szélső m elemeket garantált kell rendezni a megfelelő helyre. Ha szeretné látni ezt magadnak, tudjuk próbálni egy teljesen hátra lista [9, 6, 5, 3, 2]. Miután az egyik átmegy a teljes lista [Hang az írás] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] A jobb szélső elem 9 nyelven a megfelelő helyre. Miután a második pass-through, a 6 lesz "buborékoltatunk-up" a 2. jobb szélső helyen. A két elem a jobb oldalon - 6 és 9 - lesz a megfelelő helyekre miután az első két pass-throughs. 

Szóval, hogyan lehet használni ezt, hogy optimalizálják az algoritmus? Nos, miután az egyik iteráció a tömb hogy valójában nem kell ellenőrizni a jobb szélső elem mert tudjuk, ez rendezve. Miután két iteráció, tudjuk róla, hogy a jobb szélső két elem a helyén van. Tehát, általánosságban, miután k iteráció keresztül a teljes tömb, ellenőrzése az utolsó k eleme feleslegessé vált, mivel tudjuk, hogy ők a megfelelő helyen már. 

Szóval, ha válogatás egy sor n elemek, az első iteráció - you'll kell rendezni összes elemet - az első n-0. A második iteráció, akkor meg kell nézni az összes elemet, de az utolsó - az első n-1. Egy másik optimalizálási lehet ellenőrizni, hogy a lista már rendezve után iteráció. Ha ez már rendezve, nem kell, hogy többé iteráció végig a listát. Hogyan tudjuk ezt megtenni? Nos, ha nem teszünk semmilyen swap egy pass-through a lista, világos, hogy a lista már rendezve, mert mi nem cserélni semmit. Így biztosan nem kell rendezni újra. 

Talán lehetett inicializálni a lobogó változó úgynevezett "nem válogatják szét" a false, és változtassa igaz, ha a swap olyan elemek 1 iteráció a tömb. Vagy hasonlóképpen, hogy egy számláló, hány swap csinál bármely adott iteráció. A végén egy iteráció, ha nem cserélni bármely eleme, tudod, hogy a lista már rendezve, és kész. Bubble rendezése, mint a többi rendező algoritmus, lehet csípett dolgozni olyan elemeket, amelyek egy rendelési módszer. 

Ez azt jelenti, az adott két elem van egy módja annak, hogy azt mondják, ha az első nagyobb, egyenlő vagy kisebb, mint a második. Például, lehet rendezni az ábécé kimondásával hogy a <b, b <c, stb Vagy lehetne rendezni a hét, ahol vasárnap kevesebb mint hétfő ami kisebb, mint kedden. 

Bubble Rendezés egyáltalán nem valami hatékony és gyors válogató algoritmus. A legrosszabb eset runtime Big O n ² mert van, hogy n iteráció egy listát Ellenőrzi az összes n elem minden pass-through, NxN = n ². Ez futási idő azt jelenti, hogy az elemek száma, amit válogatás növekszik, a futási idő négyzetesen növekszik. 

De ha a hatékonyság nem egyik fő törekvése a program vagy ha csak egy kis válogatás számos elemet, lehet, hogy talál Bubble Sort hasznos, mert ez az egyik legegyszerűbb rendezési algoritmusok megérteni és a kódot. Ez is egy nagyszerű módja annak, hogy tapasztalatokat fordítására elméleti algoritmus tényleges működését kódot. Nos, ez Bubble osztályozása az Ön számára. Köszönöm, hogy néz. CS50.TV