[Musika jotzen] 

DOUG LLOYD: Beraz txertatzeko moduko bat da, algoritmoa array bat ordenatzeko erabili ahal izango dugu. Algoritmo honen atzean dagoen ideia da zure ordenatuko array eraikitzeko lekuan, aldatzearen elementu daudelarik Bide batez, joan ahala, gela egiteko. Hau da, apur bat desberdinak hautaketa ordena edo burbuila-tik ordenatu, adibidez, non kokapenak egokituz ari gara, non swaps egiten ari gara. 

Kasu honetan zer benetan gara egiten elementu irristakorra da baino gehiago, modu daudelarik. Nola algoritmo hau ez pseudocode lan? Beno dezagun arbitrarioki esan du hori array lehen elementu ordenatuko da. Eraikitzen ari gara lekuan. 

Botako elementu bat joan gara aldi berean eta eraiki da, eta beraz, ikusiko dugun lehenengo gauza elementu bat array bat da. Eta berez, bata elementu array ordenatuko da. 

Ondoren, prozesu hau errepikatu beharko dugu until-- Prozesu hau errepikatu beharko dugu elementu guztiak arte antolatuko dira. Begira hurrengo Unsorted elementu aztertu eta sartu ordenatzen zati, eskatutako kopurua aldatzearen elementu bidea out of. Zorionez bisualizazio honetan Ikusten duzu zehazki zer da lagunduko dizu gertatzen Ordena txertatzeko. 

Beraz, berriro ere, hona hemen gure osoa Sailkatu array, elementu guztiak gorriz adierazita. Eta utzi jarraitu hamarkadan Gure pseudocode pausoak. Lehenengo gauza egin dugu, hau da deitzen dugun array lehen elementu, ordenatuta. Beraz, besterik botako esan nahi dugu bost, Orain ari ordenatuko duzu. 

Ondoren, begiratu hurrengo at dugu array elementu Sailkatu eta hori sartu nahi dugun ordenatzen zati, elementu aldatzearen baino gehiago. Beraz, bi da hurrengo Unsorted array elementu. Bistan denez pertenece aurretik bost, beraz, zer egin botako Oraindik dugu moduko bi eutsi albo batera bigarren bat, filmea bost baino gehiago, eta, ondoren, bi txertatu bost aurretik, nora joan behar. Eta, esan dezakegu orain dela bi ordenatuko da. 

Beraz, ikusi ahal izango duzu, besterik ez dugu orain arte bi array elementu begiratu zion. Ez dugu begiratu zion atseden guztietan, baina dugu got bi elementu horiek horrela antolatu aldatzearen mekanismoa modu. 

Beraz, prozesua errepikatu dugu berriro. Begira hurrengo ordenatu gabe dauden elementu, hori ez da. Dezagun eutsi alde batera bigarren bat, filmea baino gehiago dena, eta jarri bat non joan behar du. 

Berriz ere, oraindik ere, bakarrik inoiz ez dugu Bat, bi, eta bost begiratu zion. Ez dakigu zer gehiago da, datozen baina hiru elementu horiek horrela antolatu dugu. 

Hurrengo elementu Unsorted da hiru, beraz, ezarri egingo dugu alde batera utzi. Egingo mugitzeko dugu zer garen behar den, oraingo honetan ez da guztia, aurreko urtean bezala Bi kasuetan, besterik ez da bost. Eta gero laburra jarri dugu, hiru, Bi eta bost artean. 

Sei da hurrengo Unsorted array elementu. Eta hain zuzen ere, sei eta bost baino handiagoa da, eta beraz, ere ez dugu edozein aldaketa egin behar. Besterik ezin dugu Tack sei egokian on ordenatzen zati amaieran. 

Azkenik, lau da azken Unsorted elementu. Beraz, ezarri dugu, eta hura alde batera utzita, filmea baino gehiago elementuen gainean mugitzeko behar dugu, eta, ondoren, jarri lau tokian. Eta orain, begira, ordenatu dugu elementu guztiak. Txertatze nabarituko ordenatu, ez genuen atzera eta aurrera array zehar joateko. Bakarrik array zehar joan ginen garai batean, eta gauza desplaza dugu jadanik genuke, ordena horretan elementu berriak egiteko lekua uzteko. 

Beraz, zein da kasu txarrena Ordena txertatzeko eszenatoki? Kasurik okerrenean ere, array alderantzizko ordenan. N elementuetako bakoitza filmea duzu n posizioak arte, behin denbora dugu bakar Txertatze bat egiteko. Hori ikusita asko da. 

Kasurik onenean ere, array primeran ordenatuko da. Eta moduko zer gertatu zen bezala bost eta sei Adibide batera, non besterik ezin dugu Tack gainean Edozein aldatzearen egin beharrik gabe, funtsean ez litzaidake. 

Imajinatu baduzu, gure array sei bidez bat izan zen, hasteko off genuke arabera Bat geratuko ordenatuko da. Bi bat ondoren dator, beraz, besterik ezin dugu esaten, OK, bai eta bi antolatuko dira. Hiru dator bi beraz, ondoren, Ados, Bat eta bi eta hiru ordenatuko dira. 

Ez gara trukeak edozein egiteko, gaude lerro arbitrarioak honetan mugitzen ordenatuko artean eta ordenatu gabe joan gara. Eraginkortasunez adibidean egin dugun bezala, elementu inflexio urdin, aurrera jarraitu dugu. Beraz, zer da kasu exekuzio txarrena, orduan? Gogoratu, bakoitza, mugitu behar badugu n elementuen seguru n postuetan, Zorionez hori ematen dizu Ideia bat kasu txarrena runtime da Big n O karratu. 

Array primeran bada ordenatuta, guztiak egin behar dugu da elementu bakoitza begiratu behin, eta, ondoren, egiten ari gara. Beraz, onena kasuan, n omega da. 

Naiz Doug Lloyd. Hau CS50 da.