[Powered by Google Translate] TOMMY: dezagun hautaketa sort begirada, algoritmo bat
zenbakien zerrenda bat hartu eta hauek ordenatzeko.
Algoritmo bat, gogoratu besterik ez da, urrats-urrats
zeregin bat lortzeko prozedura.
Aukeraketa sort oinarrizko ideia da zatitzea
gure bi zatiak sartu zerrenda -
ordenatuko zati bat eta Unsorted zati bat.
Algoritmoaren urrats bakoitzean, zenbaki bat da, mugitu
Unsorted ordenatuko zati zati azkenean arte
zerrenda osoa ordenatuko da.
Beraz, hona hemen sei zenbakien zerrenda bat da -
23, 42, 4, 16, 8, eta 15.
Oraintxe zerrenda osoa Unsorted jotzen da.
Nahiz eta 16 bezalako zenbaki bat dagoeneko bere zuzena
kokapena, gure algoritmoa modu hori ezagutu arte ez du
zerrenda osoa ordenatuko da.
Beraz, zenbaki bakoitzeko kontuan dugu Unsorted ordenatzeko arte
da geure buruari.
Zerrenda ordena gorakorrean izan nahi dugun jakin dugu.
Beraz, nahi gure zerrendaren zati ordenatuko sortu dugu
ezkerretik eskuinera, handiena txikiena.
Horretarako, gutxieneko elementu Unsorted behar dugu
eta jarri, ordenatzen zati amaieran.
Zerrenda hau ez da horrela antolatu zenetik, horretarako modu bakarra da
Unsorted zati, elementu bakoitzaren begiratu gogoratzeko
elementu da txikiena eta alderatuz
duten elementu bakoitza.
Beraz, lehen 23 begiratu dugu.
Elementu lehenengo ikusten dugu, beraz, gogoan izan dugu
gutxieneko bezala.
Hurrengo 42 bilatuko dugu.
42 23 baino handiagoa da, eta, beraz, 23 izango dira gutxienez.
Next 4 eta 23 baino gutxiago da, beraz, 4 gogoratzen dugu
gutxieneko gisa.
Hurrengoa 16 eta 4 baino handiagoa da, eta, beraz, 4
da, oraindik ere, gutxienez.
8 4 baino handiagoa da, eta 15 4 baino handiagoa da, 4 izan behar du, beraz,
Unsorted elementu txikiena.
Beraz, nahiz eta gizakiak berehala dezakegu ikusteko 4 dela
gutxieneko elementu, gure algoritmoa behar begiratzen
Unsorted elementu behin, ondoren ere aurkitu dugu, 4 -
gutxieneko elementu.
Beraz, gaur egun, gutxieneko elementu, 4 aurkitu ditudan dugu, nahi dugu.
mugitzeko zerrendaren zati ordenatzen sartu.
Hau lehen urratsa da, horrek esan nahi du, 4 jarri nahi dugu
zerrendaren hasieran.
Oraintxe bertan 23 zerrendaren hasieran da, eta, beraz,
dezagun swap 4 eta 23.
Beraz, orain, gure zerrenda hau atsegin du.
4 izan behar duela bere kokapena azken ezagutzen dugu, delako
txikiena biak elementu eta elementu hasieran
zerrendan.
Honek esan nahi du, beraz, ez dugu inoiz berriro eraman beharko.
Hargatik errepikatu prozesu honetan beste elementu bat gehitzeko
ordenatuko zerrendaren zati.
4 begiratu behar ez dugun ezagutzen dugu, delako
Dagoeneko ordenatuko da.
Beraz, 42 hasi ahal izango dugu, bezala gogoratzen dugu
gutxieneko elementu.
Beraz, hurrengo 23 eta 42 baino gutxiago bilatuko dugu, beraz,
gogoratu 23 gutxieneko berria da.
16, hau da, 23 baino gutxiago ikusiko dugu, eta, beraz,
16 gutxieneko berria da.
Orain 8 baino 16 gutxiago ikusi dugu, eta, beraz,
8 gutxieneko berria da.
Eta, azkenik, 8 15 baino gutxiago da, beraz, 8 gutxienez badakigu
Unsorted elementu.
Beraz, horrek esan nahi du 8 erantsi behar dugu ordenatzen
zerrendaren zati.
Oraintxe 4 ordenatuko elementu bakarra da, beraz, jarri nahi dugu
8 next 4.
42 geroztik Unsorted zatia lehenengo elementua da
zerrendan, 42 eta 8 swap nahi dugu.
Beraz, orain, gure zerrenda hau atsegin du.
4 eta 8 zerrendaren zati horrela antolatu, eta
Gainerako zenbakiak irudikatzeko Unsorted
zerrendaren zati.
Hargatik iterazio beste batekin jarraitzeko.
23 Une honetan, ez dugu, ez baita behar begiratzen
4 eta 8 gehiago dut dutelako
dagoeneko ordenatuko da.
16 23 baino gutxiago da, beraz, gogoan izan dugu
16 gutxienez berria.
16 42 baino gutxiago da, baina 15 baino 16 gutxiago, eta, beraz, 15 izan behar du
gutxieneko elementu Unsorted.
Beraz, gaur egun, 15 eta 23 swap nahi dugu
ematen diguten zerrenda honetan.
Zerrendaren zati ordenatuko 4, 8 eta 15 osatzen dute, eta
elementu horiek oraindik Unsorted.
Baina besterik ez da gertatzen hurrengo Unsorted elementu, 16,
dagoeneko ordenatuko da.
Hala eta guztiz ere, ez dago modurik gure algoritmoa jakin 16 dela
dagoeneko bere kokapena zuzena da, beraz, oraindik behar dugu
errepikatu prozesua bera.
Beraz, 16 42 baino gutxiago dela ikusiko dugu, eta 16 baino gutxiago 23 eta, beraz,
16 gutxieneko elementu izan behar du.
Ezinezkoa da, berez elementu honen trukatu, gaitezke, beraz
utz kokapen honetan.
Beraz, gure algoritmoa pass bat gehiago behar dugu.
42 23 baino handiagoa da, eta, beraz, 23 izan behar du
gutxieneko Unsorted elementu.
Ondoren, 23 eta 42 trukatu dugu, amaituko dugu gure azken
ordenatuko zerrenda -
4, 8, 15, 16, 23, 42.
42 leku egokian egon behar da geroztik ezagutzen dugu
elementu bakarra utzi, eta duten aukeraketa ordenatu.
Dezagun gure algoritmoa batzuk formalizatzeko
pseudocode.
On line bat, ikusi behar dugun integratzeko dezakegu
zerrendako elementu guztiak.
Azken elementu izan ezik, izan ere, 1 elementua
zerrenda dagoeneko ordenatuko da.
On line bi, Unsorted, lehenengo elementua kontuan hartzen badugu
zerrendaren zati minimoa izan da, gure genuen bezala
Adibidez, eta, beraz, zerbait alderatu dugu.
Line hiru bigarren begizta hasten den zehar batetik bestera joateko dugu
Unsorted elementu bakoitza.
Badakigu, i iterazio ondoren, ordenatuko zati
gure zerrendan elementu i Urrats bakoitzak izan behar
era askotako elementu bat.
Beraz, lehen Unsorted elementu behar posizioa i gehi 1 izango da.
Lau On line, oraingo elementu alderatu dugu gutxieneko
dut ikusi dugun elementu hain urruti.
Uneko elementu minimoa baino txikiagoa bada
elementu, ondoren, gaur egungo elementu berri bezala gogoratzen dugu
line bost gutxienez.
Azkenik, sei eta zazpi. Lerroak, gutxieneko swap dugu
elementu Unsorted lehen elementu eta, horrela,
zerrendaren zati ordenatuko gehituz.
Dugu algoritmo bat ondoren, galdera garrantzitsu bat eskatu
programatzaile gisa geure buruari zenbat denbora ez hartu?
Eskatzen dugu lehenik eta behin galdera zenbat denbora ez hartu hau
algoritmoaren kasu txarrena exekutatu?
Gogorarazten entzierro hau adierazten dugu
O big notazioa denbora.
Ordena gutxieneko Unsorted elementu zehazteko, dugu
funtsean elementu bakoitzaren alderatu izan zerrendan
zerrendako beste elementu bat behin.
Senez, n eragiketa karratu O bat bezalako soinuak hau.
Gure pseudocode begira, izan ere habiaratuak barruan loop
loop beste, hain zuzen ere soinuak O bat bezalako
n eragiketa karratu.
Hala eta guztiz ere, gogoratu baina ez dugu behar baino gehiago begiratu
zerrenda osoa gutxieneko Unsorted elementu erabakigarria?
Bazekien 4 zen horrela antolatu ondoren, adibidez, ez genuen
begiratu behar da berriro ere.
Beraz, hau ez txikiagoa exekutatzen ari den denbora?
Gure zerrenda luzera 6, bost egin behar dugu
lehen elementu konparazioak, lau konparazioak egiteko
Bigarren elementua, eta abar.
Horrek esan nahi du, urratsen kopuru osoa batura da
Osoko zenbaki 1etik zerrenda ken 1 luzera.
Summation bat irudikatu ahal izango dugu.
Ez dugu summations sartu hemen.
Baina bihurtzen da summation hori n aldiz berdina
n ken 1 2 baino gehiago.
Edo equivalently, n 2 baino gehiagoko minus n 2 baino gehiago karratu.
Exekuzio asymptotic buruz hitz egiten denean, epe karratu n
n epe honetan menderatzeko.
Beraz, aukeraketa sort O n karratu.
Gogoratu gure Adibidez, hautaketa ordena oraindik behar
egiaztatu zen kopuru hori dagoeneko horrela antolatu bada
mugitu behar dira.
Beraz, horrek esan nahi du ran aukeraketa sort bat dagoeneko baino gehiago
ordenatuko da zerrenda, urratsen kopuru bera behar luke
litzateke zerrenda erabat Unsorted baino gehiago exekutatzen ari denean.
Beraz, aukeraketa sort n karratu kasuan errendimendu onena du,
omega n karratu dugu.
Eta hori da aukeraketa sort.
Just algoritmoak asko dugu
zerrenda bat erabili ordenatzeko.
Nire izena Tommy da, eta, hau da cs50.