[Powered by Google Translate] [Insertion Sort] [Tommy MacWilliam] [Harvardeko Unibertsitateko] [Hau da CS50.TV] Dezagun txertatzeko sort begirada, zenbakien zerrenda bat hartu eta hauek ordenatzeko algoritmo bat. Algoritmo bat, gogoratu besterik ez da, urrats-urrats bat zeregin bat lortzeko prozedura. Txertatzeko sort oinarrizko ideia da, gure zerrenda zatitzeko bi zatiak, ordenatuko zati bat eta Unsorted zati bat. 

Algoritmoaren urrats bakoitzean, zenbaki bat da mugitzen Unsorted zati ordenatuko zati azkenean arte zerrenda osoa ordenatuko da. 23, 42, 4, 16, 8, eta 15 - Hemen sei zenbakiak Unsorted zerrenda da. Zenbaki horiek ez dira geroztik ordena gorakorrean, Unsorted ari dira. Dugu, oraindik ez da hasi zenetik ordenatzeko, sei elementu guztiak kontuan hartu dugu gure Unsorted zati. 

Behin ordenatzeko hasten gara, zenbaki horiek ordenatuko jarri dugu hauen ezkerraldean. Beraz, dezagun 23, gure zerrendan lehenengo elementua hasteko. Ez dugu oraindik gure zati ordenatuko edozein elementu, beraz, besterik gabe, kontuan hartu 23 gure zati ordenatuko hasiera eta amaiera izan. Orain, gure zati bat zenbakia, 23 ordenatuko ditu, eta gure Unsorted zati ditu bost zenbaki horiek. Dezagun gaur egun gure zati Unsorted, 42, sartu hurrengo zenbakia ordenatzen zati bihurtu. 

Horretarako, 42 23 konparatu behar dugu -, gure zati ordenatuko elementu bakarra orain arte. Berrogeita bi 23 baino handiagoa da, eta, beraz, besterik gabe, ahal izango dugu eransteko 42 amaiera zerrendaren zati ordenatzen. Great! Orain gure ordenatuko zati bi elementu ditu, eta gure Unsorted zati lau elementu ditu. Beraz, dezagun orain 4 mugitzeko, Unsorted zati hurrengo elementua. Beraz, non behar ordenatuko zati jarri? 

Gogoan izan, zenbaki hau jarri nahi dugu, ordena ordenatuko beraz, gure ordenatuko zati izaten jarraitzen du, une oro behar bezala ordenatuko. 4 42 eskubidea jartzen dugu, eta gero, gure zerrendan izango da ordena. Beraz, dezagun gure sort zati eskuinetik ezkerrera mugitzen jarraituko. Mugitu dugun bezala, dezagun, mugitu zenbaki bakoitza gela leku bat behera egin zenbaki berria. Ados, 4 da 23 baino gutxiago ere, eta, beraz, ezin dugu kokatu hemen bai. Dezagun 23 bat eskuinera leku mugitu. 

Horrek esan nahi du slot sartu lehen zati ordenatzen 4 kokatu nahi genuke. Ohartu zerrenda espazio hau dagoeneko hutsik zen, dugu delako horrela antolatu elementuak mugituz jaitsiko dugu aurkitu bezala. Guztiak eskubidea. Beraz, erdibidean ez gara. Dezagun gure algoritmoa 16 txertatzeak ordenatzen zati sartu. Hamasei baino gutxiago 42, eta, beraz dezagun filmea 42 eskuinera. Hamasei ere 23 baino gutxiago da, eta, beraz dezagun ere mugitzeko elementu hori. 

Orain, 16 4 baino handiagoa da. Beraz, 4 eta 23 artean 16 sartu dugu gustatuko litzaidake bezala ikusten da. Zerrendaren zati ordenatzen bidez eskuinetik ezkerrera mugitzen ari den bitartean, 4 ikusi dugu lehenengo zenbaki kopurua baino txikiagoa da txertatzeko saiatzen ari gara. Beraz, gaur egun 16 sartu ahal izango dugu hau hutsik zirrikituan gogoan, elementu hunkigarria dugu sortu sort zati baino gehiago Nik ez dugu aurkitu ditu. 

Guztiak eskubidea. Orain, lau ordenatuko elementu eta bi elementu Unsorted dugu. Beraz, dezagun mugitu 8 ordenatzen zati sartu. Zortzi 42 baino gutxiago da. Zortzi 23 baino gutxiago da. Eta 8 16 baino gutxiago da. Baina 8 4 baino handiagoa da. Beraz, 8 sartu nahi genuke, 4 eta 16 bitartean. Eta orain, besterik ez dugu bat elementu gehiago utzi ordenatzeko - 15. Hamabost baino 42 gutxiago, hau da, Hamabost 23 baino gutxiago da. Eta 15 baino gutxiago 16 urtekoa da. Baina 15 8 baino handiagoa da. 

Beraz, hemen da non gure azken txertatzeko egin nahi dugu. Eta Bukatutakoan dugu. Unsorted zati elementu gehiago ez daukagu, eta gure orden egokian zati ordenatuko da. Txikiena etatik handiena agindu zenbakiak. Beraz, dezagun begirada bat egin besterik ez dugu urratsak deskribatzen batzuk pseudocode. 

On line 1, ikus zerrendako elementu bakoitza baino gehiago batetik bestera joateko dugun behar dugu lehen ezik, Unsorted zati lehen elementu bihurtu baita, besterik gabe, ordenatzen zati lehenengo elementua. 2 eta 3 lerro On, pista ari gara mantenduz gure uneko Unsorted zati leku. Element ari ordenatzen zati mugitzen zenbakia adierazten du, eta j gure indizea adierazten Unsorted zati batean. 

On line 4,, eskuinetik ezkerrera zati ordenatzen bidez ari gara errepikatzean. Elementu behin gure uneko posizioa ezkerreko errepikatzean geldiarazi nahi dugu sartu saiatzen ari gara elementu baino gutxiago. On line 5, elementu bakoitza espazio bat aurkituko dugu eskuinera aldatzearen ari gara. Horrela, argi eta garbi espazioa sartu sartu izan dugu aurreneko elementu aurkituko ditugu mugitzen ari gara elementu baino gutxiago. On line 6, gure counter eguneratzen ari gara ordenatzen zati bidez ezkerrera mugitzeko jarraitzeko. Azkenik, linea 7, elementu ari gara txertatzen zerrendaren zati ordenatzen sartu. 

Posizioa j txertatzeko dela ongi ezagutzen dugu, dugu dagoeneko elementu egon espazio bat eskuinera mugitu. Gogoratu, eskuinetik zati ordenatuko bidez ari gara ezkerrera mugitzen baina, ezkerretik eskuinera zati Unsorted bidez mugitzen ari gara. Guztiak eskubidea. Dezagun gaur egun zenbat denboraz algoritmoa izan zen exekutatzen ari begirada bat hartu. Eskatzen dugu lehenik eta behin galdera zenbat denbora du algoritmo hau kasurik okerrenean exekutatu. Gogoratu O Big notazioa ordezkatzen dugun exekutatzen ari da une honetan. Gure zerrenda ordenatzeko, Unsorted zati elementu batetik bestera joateko behar izan genuen, eta elementu horiek bakoitzaren, potentzialki ordenatzen zati elementu guztiak baino gehiago. Senez, bat O (n ^ 2) eragiketa bezalako soinuak hau. 

Gure pseudocode begira, begizta bat beste baten barruan habiaratu begizta bat dugu, horrek, hain zuzen ere, bat O (n ^ 2) eragiketa bezala soinuak. Hala eta guztiz ere, zati zerrendan ordenatuko ez du oso amaiera arte zerrenda osoa. Hala eta guztiz ere, potentzialki izan dugu elementu berri bat sartu ordenatzen zati hasieran algoritmoaren iterazio bakoitzean, horrek esan nahi du elementu bakoitza begiratu gaur egun zati ordenatzen dugun litzaidake. Beraz, horrek esan nahi du, potentzialki bigarren elementu bat konparaketa egin ahal izan genuen, hirugarren elementu bi konparazioak, eta abar. Beraz, urratsen kopuru osoa, zenbaki osoen batura 1etik zerrenda ken 1 luzera da. Summation bat irudikatu ahal izango dugu. 

Ez dugu summations sartu hemen, baina bihurtzen da summation dela berdina n (n - 1) 2 baino gehiago, hau da, baliokideak n ^ 2/2 - n / 2. Exekuzio asymptotic buruz hitz egiten denean, n ^ 2 epe n epe honetan menderatzeko. Beraz, txertatzeko ordena Big O (n ^ 2) da. Zer ran txertatzeko sort dagoeneko horrela antolatu zerrendan. Kasu horretan, nahikoa genuke eraikitzeko zati ordenatuko ezkerretik eskuinera. Beraz, soilik n urratsak ordena behar dugu. 

Horrek esan nahi du txertatzeko sort n errendimendua best-kasu bat, Ω (n) dugu. Eta hori da txertatzeko sailkapenarentzat, hainbat algoritmo bat zerrenda ordenatzeko erabili ahal izango dugu. Nire izena Tommy da, eta hau da CS50. [CS50.TV] Oh, ezin besterik ez duzu ez gelditzeko behin hasten da. Oh, genuen - >> Boom!