[Powered by Google Translate] [Batu Sort] [Rob Bowden - Harvard Unibertsitatea] [Hau CS50 da. - CS50.TV] Dezagun merge sort buruz hitz egiteko. Orain arte ikusi duzun burbuila ordenatu, txertatzeko, ordenatu, eta aukeraketa sort. Zer esan nahi hobea dut nire eskua uhin mota dut arren, batu sort, oro har, 3 mota horietako edozein baino hobea egiten du. 

Baina merge sort buruz hitz egin baino lehen, dezagun 2 ordenatuko zerrendak batuz buruz hitz egiteko. 2 ordenatuko zerrendak hartzeko prozesua deitu dugu, horrelako eta zerrenda bakar batean ordenatuko horietako zerrendak batuz. Nola egin dezakegu hori? Beno, ideia bat da, besterik gabe itsasten zerrenda bat beste zerrenda amaiera aldera eta, ondoren, ordenatzeko sortutako zerrenda. 

Honetan lan egiten ari den bitartean, alferrikako lan asko da. Egin ahal izango dugu azkarrago besterik ez ordenatzeko baino. Iragarki bat okerreko ideia hori hartu txandakatuz cups zerrenda bakoitzaren. Obrak bezala bitartean, badirudi lehen, oharra, 16 eta 23 leku daude amaituko dugun, 4, 8, 15, 23, 16 egiten ari dira. Hau da, 2 partiduko agertzen zerrendan batu behar elementu delako hasierako zerrendan daude. Biak 15 eta 16 ezkerreko zerrendan daude. Trick da aprobetxatu Izan ere, zerrendak, bai ordenatuko dira dagoeneko. Horrek esan nahi du besterik ez dugu zerrendak bi elementu lehenengo bada itxura - Hemen, 4 eta 8 - horietako bat ere batu zerrendaren lehenengo elementua izan behar du. Beno, zergatik da hori? Bi zerrenda horiek jada ordenatuta, eta, beraz, bai 4 edo 8 elementu txikiena izan behar du, 2 zerrendak konbinatzen ditugu. Kasu honetan, txikiena 4 da, beraz, atera ahal izango dugu 4 eta egiteko, gure zerrendan batu lehenengo elementua. Orain 3 lehenengo zerrendako gainerako elementuak batuz jarraitzen dugu Bigarren zerrenda 4 elementuak. 

Berriro ere, zerrendak, bai lehen elementu begiratu besterik ez dugu behar. 2 txikiagoa batu gure zerrendan bigarren elementua izan behar du. Oraingo honetan, 8 eta 15 artean txikiena 8 izango da, eta gu sartu gure zerrendan ordenatuko bigarren elementu gisa. Zerrendak bi elementu lehenengo alderatzen jarraituko dugu eta 2 txikiagoa kendu. 15 eta 23, 15 alderatuz txikiagoa da eta, beraz, hori da gure hirugarren elementu. Orain 16 alderatuz, eta 23, 16 txikiagoa da. Beraz, laugarren elementua da. 

Hasiera 2 elementu zerrenda berean errenkadan etorri ziren. Hau da, zergatik batu zerrenda ezin 2 zerrendak elementu ordezko. , 23, 50 eta 23. Alderatuz txikiagoa da eta, beraz, aukeratuko dugu. 50 eta 42 urte bitartean, 42 txikiagoa da. 50 eta 108 bitartean, 50 txikiagoa da. Eta, azkenik, besterik ez dugu 108, beraz, gure zerrendaren amaieran behar da. Iragarki polit bat, zerrenda ordenatuko ditugu. 2 2 zerrendak lehen elementuak alderatu dugu denbora bakoitza Batutako zerrenda hurrengo elementua zehazteko gai izan ginen. Horrek esan nahi du, bada behin betiko zerrenda hori du n zenbakiak, non n hemen, 8, ondoren n gehien konparaketak behar dugu zenbaki horiek guztiak leku egokian. Algoritmo bat, besteak beste, esan duenez, denbora lineal exekutatu, baina ez kezkatu horregatik. 

Konbinatzeko gure algoritmoa erabiliz, azkar merge sort algoritmoa egin ahal izango dugu. Beraz, dezagun berrezarri gure zerrendak. 2 merge sort prozesuan urrats handiak daude. Lehenik eta behin, etengabe zatitu cups zerrenda halves sartu horietan kopa 1 besterik ez dugu zerrendak sorta bat arte. Ez kezkatu zerrenda batean bakoitiak zenbaki bat badu eta ezin duzu haien arteko ebaki primeran garbi bat egiteko. Just arbitrarioki hautatzeko zerrenda extra kopa sartu, besteak beste Beraz, dezagun zatitu, zerrenda horiek. Orain 2 zerrendak dugu. Orain 4 zerrendak dugu. 

Eta orain, 8 zerrendak dugu zerrenda bakoitzean kopa bakar bat. Beraz, urrats 1. Urratsa 2, behin eta berriz batu ditugu bikote zerrendak merge aurretik ikasi dugu algoritmoa erabiliz. 108 eta 15 biltzen, amaituko dugu zerrendan 15, 108. 50 eta 4 biltzen, 4, 50 amaituko dugu. 8 eta 42 biltzen, amaituko dugu 8, 42. Eta 23 eta 16 batuz, azkenean 16, 23. Orain gure zerrendak tamaina 2. Iragarki 4 zerrendak ordenatuko bakoitza. 

Beraz, zerrendak bikoteak batuz berriro hasi ahal izango dugu. 15 eta 108 eta 4 eta 50 biltzen 4 lehenengo hartu eta, ondoren, 15, eta gero 50, gero, 108. 8, 42 eta 16, 23 biltzen lehen aldiz hartu dugu 8, ondoren, 16, 23, eta gero 42. Beraz, orain 2 tamaina 4 zerrendak besterik ez ditugu, eta bakoitzak bere ordenatuko da. Beraz, gaur egun, 2, zerrenda horiek batu ditugu. Lehenik eta behin, 4 hartuko dugu. Ondoren, 8 hartuko dugu. Ondoren, 15 eta 16, eta gero 23, gero 42, gero 50, gero 108 hartuko dugu. Eta Bukatutakoan dugu. Zerrenda ordenatuko dugu. Beraz, nola azkar izan zen hau, zehazki? Termino tekniko, merge sort O (n log n), burbuila ordenatu, txertatzeko, ordenatu, eta aukeraketa sort guztiak ez dira, berriz,: O (n ²). Izan ere, laster ikasi dugu, ez da izango duzu ahal izango moduko bat etorri egiten O (n log n) baino hobeto kasu orokorra. Berriz ere, ez kezkatu O big notazioa ikusi ez baduzu oraindik. 

Just jakin nahi izan dugu, horrek esan nahi du benetan big zerrenda ordenatzeko nahi izanez gero burbuila ordenatu, txertatzeko, ordenatu, eta aukeraketa sort izan potentzialki hartu nabarmen longer batu baino sort. Horrek ez du esan nahi merge sort azkarrago zerrenda guztietan izango da edo nahiz eta tamaina jakin batekin edozein zerrenda bakarrean. Esate baterako, txertatzeko ordena zerrenda guztietan 5 elementu baino txikiagoa sort azkarrena izan daiteke. Praktikan, merge sort 50 elementu gisa txiki gisa zerrendak izan ohi da azkarrago. 

Hala ere, abiadura hau gehigarria ez du prezio bat gabe iritsi da. Gure ordenatzen beste ez bezala, zerrenda bat hartu eta leku zerrenda aldatu ordenatuko zerrenda bat lortu arte, merge sort lekua behar du osagarria 2 zerrendak batu elkarrekin. Ezin dugu berehala erabiltzen ari diren zerrendak fusionatuko Batutako zerrenda gordetzeko oraindik behar duten elementuak fusionatzen behar dugu gainidatz dezake geroztik. Espazio hau prezio bat pixka bat da, baina normalean ez da arrazoizkoa. Eta hori merge sort. 

Nire izena Rob Bowden da, eta hau da CS50. [CS50.TV] Eta aukeraketa sort. [Barreak] Oh, baina hori atera ere pizten dut nola nengoen aurkezten duelako. Ezkerreko zerrendan. Hori typo izan zen. [Misspoke] izorratu I - [Barreak] Ez dakit zer