>> [Musika jotzen]
DOUG LLOYD: Ondo da, beraz, burbuila sort algoritmoa da
elementu multzo bat ordenatzeko erabili ahal izango duzu.
Ikus dezagun nola funtzionatzen duen begirada bat.
>> Beraz, oinarrizko ideia atzean burbuila sort da hau.
Oro har, goi-mailako eraman nahi dugu baloratzen, oro har, eskubidea elementuak,
eta baloratzen elementu jaistea, oro har, ezker, jo genuen espero.
Behekoan gauzei egon nahi dugu hasieran, eta goi-mailako gauzak
amaieran izan.
>> Nola egiten dugu hau?
Beno pseudocode kodea ere, esan genezake, dezagun
swap ez-zero balio bat kontagailu bat ezartzeko.
Ikusiko dugu zergatik egiten dugun bigarren bat ere.
Eta gero, honako hauek errepikatu dugu Prozesu swap kontagailua 0 izan arte,
edo swaps ez dugu egin arte guztietan.
>> Berrezarri swap kontagailu 0 ez bada dagoeneko 0.
Ondoren, begiratu at guztietan ondoko elementu pare.
Bi elementu horiek dira bada Ez ordenan, trukatzeko,
eta gehitu 1 swap mostradorera.
Zuk pentsatzen bada hau ikusmenarekin aurretik,
nabarituko hori txikiagoa dela mugituko da baloratzen ezkerreko elementu
eta goi-mailako baloratzen eskubidea elementuak, eraginkortasunez zer egin nahi dugun egiten,
hau da, talde horiek mugitu horrela elementuen.
Dezagun ikusteko nola hau gure array erabiliz begiratu dezake
Hori probatzeko erabiliko dugu Algoritmo horien out.
Sailkatu array bat dugu hemen, berriz, elementu guztiak bidez adierazten
Gorriz izatea.
Eta ezarri dut nire swap counter nulua balio bat.
Arbitrarioki aukeratu nuen negatiboa 1-- ez da 0.
Prozesu hau errepikatu nahi dugu 0 da swap counter arte.
Hori dela eta, nire swap ezarri dut Zero ez balio batzuk kontraerasoan,
Bestela delako swap counter 0 izango litzateke.
Ez genuke ere hasiko du Algoritmoaren prozesua.
Beraz, berriro ere, pausoak are-- berrezarri swap mostradorera
0, orduan ondoko bakoitzean begiratu bikotea, eta ari dira barrutitik kanpo egonez gero,
trukatzeko, eta gehitu 1 swap mostradorera.
Hargatik hasiko prozesu honetan.
Beraz, lehenengo gauza egiten dugu swap counter ezarri dugu 0,
eta, ondoren, bila hasten gara aldameneko pare bakoitzean.
>> Beraz, lehen hasten gara 5 eta 2 begira.
Direla daudelarik ikusi dugu aginduko du eta, beraz, trukatu dugu.
Eta gehitzen badiogu 1 swap mostradorera.
Beraz, orain gure swap counter 1 da, eta 2 eta 5 aktibatu dira.
Orain, prozesua errepikatu dugu berriro.
>> Begiratu hurrengo aldameneko pare batean gaude, 5 eta 1 halaber ordena Oraindik dute,
beraz, horiek aldatu dugu eta gehitu 1 swap mostradorera.
Ondoren, begiratu 5 eta 3 dugu.
Dira dute ordena, beraz trukatu ditugu haiek eta guk gehitu 1 swap mostradorera.
Ondoren, begiratu 5 eta 6 dugu.
Oraindik ordena dutela, beraz, ez dugu benetan trukatzeko ezer une honetan behar.
Ondoren, begiratu 6 eta 4 dugu.
Oraindik ere ordena, beraz trukatu ditugu haiek eta guk gehitu 1 swap mostradorera.
>> Orain konturatu zer gertatu zen.
Nik egin dugu jauzi 6 modu guztiak amaieran.
Beraz, aukeraketa ordenatu batean, dut ez baduzu bideo hori ikusi, zer egin genuen
Bukatu dugu mugituz Eraikin txikiena elementu
ordenatzen array funtsean bertatik Ezkerretik eskuinera, handiena txikiena.
Burbuila moduko kasuan, berriz, bagaude Algoritmo bereziki, honako hau,
benetan ari gara eraikitzen joan eskubidea ordenatuko array
Ezkerretik, handienetik txikienera.
Dute eraginkortasunez bubbled dugu 6an, balio handiena, amaieran modu guztiak.
>> Eta, beraz, ez dugu orain deklaratu ahal Hori ordenatuko
eta etorkizun iterations-- array igaro, berriro
ez dugu 6 kontuan hartu behar dira jada.
Kontuan hartu beharreko bakarra daukagu Unsorted elementu
denean ari gara ondoko bikote begira.
Beraz, inork amaitu dugu burbuila ordenatu pasatzen.
Beraz, orain, atzera egingo dugu galderari, errepikatu swap kontagailua 0 izan arte.
Beno swap mostradorera 4 da, beraz goaz
Prozesu hau berriro errepikatuz mantentzeko.
>> Swap counter berrezartzeko goaz 0 eta aldameneko bikote bakoitzak begiratu.
Beraz, hasteko, 2 eta 1 dugu ari dira ordena, beraz trukatu dugu
eta 1 gehitzen badiogu swap mostradorera.
2 eta 3, ari ordena dutela.
Ez dugu ezer egin behar.
3 eta 5 ematea komeni da.
Ez dugu behar ezer ez egin.
>> 5 eta 4 out dira ordenaren, eta, beraz, ez dugu
horiek aldatu eta gehitu behar 1 swap mostradorera.
Eta orain mugitu dugu 5 hurrengo elementu handiena da,
Unsorted zati amaierara arte.
Beraz, gaur egun ez diegu ordenatzen zati zati.
>> Orain ikusten ari zara pantaila eta seguruenik esango,
Ezin dut, array gisa oraintxe ordenatuko da.
Baina ezin dugu frogatu duen oraindik.
Ez dugu bermea dute Dela ordenatuta.
Baina hori da, non swap counter ari den jokoan sartzen joan.
>> Beraz pass bat amaitu dugu.
Swap mostradorera 2 da.
Beraz, errepikatu egingo da Prozesu honetan, berriz ere,
errepikatu swap kontagailua 0 izan arte.
Berrezarri swap kontagailua 0.
Beraz, berrezarri egingo dugu.
>> Orain begiratu ondoko pare bakoitzean.
Duten ordena da, 1 eta 2.
2 eta 3 ematea komeni da.
3 eta 4 ematea komeni da.
Beraz, puntu honetan, nabarituko amaitu dugu aldameneko pare guztietan begiratzen,
baina swap counter 0 dago oraindik.
>> Ez badugu dute aldatzeko edozein elementu, orduan
behar du izan, by hortaz.
Eta beraz, era askotako eraginkortasuna, dugu informatikariak hori maite,
da gainera gaur deklaratu ahal baldintza hauek bete beharko sorta osoa
ordenatuko dira, ez baikenuen delako Edozein elementu trukatu dituzte.
Hori nahiko polita.
>> Beraz, zein da kasu txarrena burbuila sort kasua?
Kasurik okerrenean array da Erabat alderantzizko ordenan,
eta, beraz, bakoitzaren burbuila behar dugu elementu handiak guztiak
array zehar modu.
Eta guk eraginkortasunez halaber behar burbuila elementu txiki guztiak atzera
array zehar modu guztiak, too.
Beraz, n elementu bakoitzari ditu mugitzeko n beste elementu guztietan.
Beraz, hori kasu okerrena da.
Kasu honetan onena eszenatoki arren, hau da,
hautaketa ordena desberdina.
Array da dagoeneko ordenatuko denean ere joaten gara.
Guk ez dugu izan inolako egiteko lehen pass swaps.
Beraz, nahi den begiratu behar dugu elementu gutxiago at, ezta?
Ez dugu hau errepikatu beharko prozesatu baino zenbat aldiz.
>> Beraz, zer esan nahi du horrek?
Beraz, zein da kasu okerrena burbuila ordenatu, eta zer da
kasu burbuila ordenatu eszenatokia onena?
Ba hau asmatzen duzu?
Kasurik okerrenean batetik bestera joateko behar duzu n elementuak n uneoro zeharkatuz.
Beraz, kasu txarrena karratu n.
>> Array primeran bada ordenatuko arren, zuk bakarrik
den bakoitzean begiratu dute elementuen behin.
Eta swap counter da oraindik bada 0, esan dezakezu array hau ordenatuko da.
Eta beraz, kasurik onenean ere, hau da, benetan aukeraketa baino hobeto
orain arte bezala n omega da.
>> Naiz Doug Lloyd.
Hau CS50 da.