[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