>> MARK GROZEN-SMITH: Kaixo, naiz Mark Grozen-Smith, eta hau da, Quicksort.
Just txertatzeko sort eta burbuila bezalako ordenatu, Quicksort algoritmo bat da
Zerrenda edo gauzak array bat ordenatzeko.
Sinpletasunagatik, Demagun dutenak Gauzak osokoak besterik ez dira, baina
Ezagutzen Quicksort lan egiten duten zenbakiak baino zerbait gehiago.
Quickstart pixka bat zailagoa da baino txertatzeko edo burbuila, baina da
ere askoz eraginkorragoa kasu gehienetan.
Itxaron segundo bat.
Ba, besterik gabe esan zuen "gehien Kasu, "ez" guztiak "?
Interesgarria, ez.
Ez kasu guztietan berdinak dira.
Ez xehetasuna hau kezkatu baduzu ez dute ikusi big O idazkera oraindik, baina
Quicksort O bat (n karratu) algoritmoa da txarrena at, besterik ez bezalakoa
txertatzeko edo burbuila ordenatu.
Hala ere, normalean askoz gehiago jokatzen du analogikoa m zaharra algoritmo bat bezala.
Zergatik?
Horretan itzuli geroago dugu.
Baina orain, dezagun ikasi nahiko luke Quicksort nola funtzionatzen.
>> Hargatik oinez hau Quicksorting bidez zenbaki osoen array txikiena etatik
handiena da.
Hemen zenbaki osoko 6 dugu, 5, 1, 3, 8, 4, 7, 9, eta 2.
Lehenik eta behin, azken elementua jaso dugu array hau - Kasu honetan, bi -
eta deitu "pibota." duen Hurrengo, dugun hasteko bi gauza begiratu -
bata, indize baxuena, hau aipatzeko dut nahi eskuinean dagoen ostatu gisa
horman, eta, bi, ezkerreko elementua, eta horrek "oraingoa deitu dizut
elementua. "Zer egin behar dugu, beste elementu guztiak, beste itxura
pibota baino, eta elementu guztiak jarri to pibota baino txikiagoa
hormaren utzi eta horiek guztiak to pibota baino handiagoa
hormaren eskuinaldean.
Ondoren, azkenik, pibota erortzen egingo dugu eskuineko horma dutela arteko jarri on
zenbaki guztietan, hura baino txikiagoa eta zenbaki guztietan handiagoa.
>> Hacerlo en duten utzi.
Hartu 2, jarri hormaren at , eta hasieran deitu 6 "uneko
elementua. "Beraz begiratu nahi dugu Gure gaur egungo elementu, 6.
Eta baino handiagoa da geroztik 2, hori utzi, han joan
hormaren eskuinera.
Ondoren, mugitzen dugu 5era gisa begiratu gure egungo elementu eta ikusi duten honetan
da, berriz ere, pibota baino handiagoa, hain dugu utzi non da eskuin bozkatu,
hormaren alde.
Mugitzen dugu.
Gure gaur egungo elementu da gaur egun 1, eta - oh.
Hau desberdina da orain.
Egungo elementu baino txikiagoa da gaur pibota, beraz, jarri nahi dugu
hormaren ezkerrera.
Horretarako, utzi piztu besterik hamarkadaren indize txikiena duen egungo elementu
besterik hormaren eskuinera eserita.
Orain, horma mugitzen dugu indize bat sortu beraz, 1 ezkerrean dago
Horman, orain alde.
>> Itxaron.
Nahasten dut besterik ez da elementu eskuineko hormaren alde, ez?
Ez kezkatu.
Hori da isuna.
Du axola buruz dugun oraingoz gauza bakarra da, elementu horiek guztiak
hormaren eskuinaldean handiagoak dira pibota baino.
Ez dago benetako ordena oraindik onartuta dago.
>> Orain, ordenatzeko itzuli.
Beraz, aurrera jarraituko dugu begira elementuetako gainerako.
Eta kasu honetan, ez direla ikusten dugu baino ez du beste elementu gutxiago
pibota, beraz, horiek guztiak utzi dugu hormaren eskuinaldean.
Azkenik, lortu uneko elementua dugu eta ikusi pibota dela.
Orain, horrek esan nahi du bi dugula array, lehenengo izaki atal
pibota da eta ezkerreko aldean txiki horman, eta bigarren izatearen
to pibota batekoa baino handiagoa eskuineko hormaren alde.
Arteko pibota elementua jarri nahi dugu biak, eta orduan jakingo dugu
pibota bere eskubidea da final ordenatuko leku.
Beraz, egiten duen lehenengo elementua aldatzeko dugu eskubidea pibota duten harresiaren alde,
eta badakigu pibota en bere eskuineko posizioa.
>> Ondoren errepikatu dugu prozesu hau egiteko subarrays utzi eta pibota eskuinean.
Geroztik azken subarray bakarra da elementu luzeak, badakigu hori da dagoeneko
nola egin dezaket izarrekin izango duzu ordenatuko delako aginduko Oraindik elementu bat besterik ez bada?
Subarray eskuinaldean egiteko, dugu ikusi pibota dela 5 da, eta hormaren
besterik ez da 6 du utzi.
Eta egungo elementu ere hasten 6 gisa.
Beraz, 6 5 baino handiagoa da.
Hori utzi, non da bozkatu, eskuineko hormaren alde.
Orain, mugitzea, 3 5 baino txikiagoa da.
Beraz pizten dugu lehen elementu batzuekin besterik hormaren eskuinaldean.
Orain, horma mugitu dut izan da.
Orain, mugitzea 8 arte.
8 5 baino handiagoa da, eta horrela utziko dugu.
4 5 baino txikiagoa da, beraz, piztu dugu.
Eta on.
>> Aldi bakoitzean prozesua errepikatu dugu on ezkerreko eta eskuineko array alboetan. dugu
pibota bat aukeratu eta konparazioak egin eta beste maila bat utzi sortu eta
eskubidea subarrays.
Dei errekurtsiboa honetan egingo arte jarraituko Azkenean denean dugu iritsiko gara
banatzen sortu array orokorrean sartu luzera 1 of subarrays besterik.
Hortik aurrera, badakigu array ordenatuko da elementu guztietan duelako, at
noizbait, pibota izan da.
Bestela esanda, elementu bakoitzeko, guztiak ezkerrera zenbakiak txikiagoan dira
balioak eta joan zenbaki guztiak eskubidea balore handiagoa izan.
>> Metodo hau oso ondo funtzionatzen du bada aukeratu pibota balioa da
erdian, gutxi gorabehera, zerrenda balioen sorta.
Hori esan nahi du, mugitzen dugu ondoren elementuen inguruan, badira asko bezala buruz
pibota ezkerraldeko elementu Han eskuinera diren bezala.
Eta arrail-eta-konkistatzen izaera Orduz Quicksort algoritmoa hartu da
abantaila osoa.
Hau O of exekuzio bat sortzen du (n log n,) 1 Egin behar dugun n ken n duelako
belaunaldi eta log bakoitzean konparazioak zerrenda zatitzeko dugu n delako
log n aldiz.
Hala ere, kasu txarrenean, hau algoritmoa benetan be O (n
karratu.) belaunaldi bakoitzean Demagun, pibota Beraz, zerbait gertatzen ahal izango du
txikiena edo handiena zenbakiak ordenatzeko ari gara.
Hau zerrendan behera hautsi esan nahiko luke n aldiz eta making n ken 1
konparazioak aldi bakoitzean bakarra.
Horrela, n o karratu.
>> Nola daiteke metodoa hobetzen dugu?
One modu ona metodoa hobetzen da behera moztu probabilitatea on duten
exekuzio da inoiz benetan n o karratu.
Gogoratu hau txarrena, txarrena kasuan agertokia bakarrik gerta daiteke noiz
aukeratu pibota da beti altuena edo matrizearen balio baxuena.
Hau da gutxiago gertatuko bermatzeko, pibota aurki ditzakegu arabera
elementu anitz eta aukeratzerakoan mediana balioa hartuz.
>> Nire izena Mark Grozen-Smith da, eta hau da CS50.
>> Sinpletasunagatik, Demagun dutenak Gauzak osokoak besterik ez dira, baina
Ezagutzen Quicksert duten -
Quicksert?
Barkatu.
>> Hemen osokoak dugu 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Benetan?
>> HIZLARIA 2: Ez gelditu.
>> HIZLARIA 1: Benetan?