[Daqq tal-mużika] 

Doug LLOYD: OK, so jingħaqdu sort għadu algoritmu ieħor li nistgħu nużaw biex issolvi l l-elementi ta 'firxa. Imma kif aħna ser tara, huwa ltqajna differenza fundamentali ħafna minn sort għażla, bubble sort, u sort inserzjoni li jagħmilha verament pretty għaqlija. 

L-idea bażika wara jingħaqdu sort huwa li sort arrays iżgħar u mbagħad għaqqadhom dawk arrays flimkien, jew jingħaqdu them-- għalhekk il-name-- sabiex Issortjat. Il-mod li jingħaqdu sort ma dan huwa billi jwieżen għodda imsejħa recursion, li huwa dak li aħna qed tmur biex jitkellem dwar dalwaqt, imma aħna ma verament tkellem dwar s'issa. 

Hawn il-idea bażika wara sort jingħaqdu. Sort in-nofs tax-xellug tal-firxa, jekk wieħed jassumi n hija akbar minn 1. U dak li jfisser meta ngħidilhom jekk wieħed jassumi n hija akbar minn 1 huwa, I think we jistgħu jaqblu li jekk firxa biss jikkonsisti minn element wieħed, huwa magħżula. Aħna ma attwalment bżonn li tagħmel xejn miegħu. Nistgħu biss tiddikjaraha li jiġu magħżula. Huwa biss element wieħed. 

Allura l-pseudocode, għal darb'oħra, huwa sort l-nofs xellug tal-firxa, imbagħad isolvi l-nofs tal-lemin tal-firxa, imbagħad jingħaqdu l-żewġ nofsijiet flimkien. Issa, diġà inti tista 'tkun ħsieb, dan it-tip ta 'ftit ħsejjes simili int tqegħid off the-- int mhux attwalment tagħmel xejn. Inti qed tgħid sort ix-xellug nofs, sort in-nofs lemini, imma int ma javżak me kif inti qed tagħmel dan. 

Imma ftakar li sakemm firxa hija element wieħed, nistgħu tiddikjaraha magħżula. Imbagħad nistgħu biss għaqqadhom flimkien. U li attwalment l- idea fundamentali wara sort jingħaqdu, huwa li din tinqasam hekk li arrays tiegħek huma ta 'daqs wieħed. U allura inti jerġgħu jinbnew minn hemm. 

Jingħaqdu sort huwa definittivament algoritmu kkumplikata. U huwa wkoll ftit ikkumplikat biex Ħares. Hekk nisperaw, il-viżwalizzazzjoni li I hawn ser jgħinek ssegwi tul. U jien ser nipprova aħjar tiegħi sabiex narrate affarijiet u jipproċedi permezz ta 'dan ftit aktar bil-mod minn dawk l-oħra biss li nisperaw tikseb ras tiegħek madwar l-ideat wara sort jingħaqdu. 

Allura aħna għandna l-istess firxa bħall- issortjar videos oħra algoritmu them-- jekk inti stajt tidher firxa sitt element. U l-kodiċi pseudocode tagħna hawnhekk hija sort in-nofs tax-xellug, issolvi l-nofs tal-lemin, jingħaqdu l-żewġ nofsijiet flimkien. Mela ejja tagħti din briks skur ħafna aħmar firxa u sort l-nofs xellug ta 'dan. 

Allura għalissa, aħna qed tmur li jinjora l-għalf fuq il-lemin. Huwa hemmhekk, imma aħna qed mhux f'dak il-pass għadu. Aħna mhux fil sort l nofs tal-lemin tal-firxa. Aħna fil sort ix-xellug nofs il-firxa. U biss għall-fini li tkun ftit aktar ċara, so I tista 'tirreferi għal dak il-pass aħna qed fuq, Jien ser jaqilbu l- kulur ta 'dan is-sett għal oranġjo. Issa, aħna qed għadhom jitkellem dwar il- istess nofs xellug tal-firxa oriġinali. Imma jien bit-tama li billi tkun tista ' jirreferu għall-kuluri ta 'oġġetti varji, dan ser jagħmilha ftit aktar ċar x'inhu għaddej hawn. 

OK, hekk issa għandna tlieta firxa element. Kif nistgħu sort l-nofs xellug ta 'din firxa, li għadu dan il-pass? Aħna qed tipprova issolvi ix-xellug nofs il-array-- briks aħmar in-nofs tax-xellug tagħha Stajt issa kkulurita oranġjo. 

Well, nistgħu nippruvaw u irrepeti dan il-proċess mill-ġdid. Allura aħna qed għadhom fil- nofs ta 'tipprova sort in-nofs tax-xellug tal-firxa sħiħa. Il-half-xellug tal- firxa, jien biss ser li jiddeċiedi arbitrarjament li l-nofs xellugi se jkun iżgħar mill-nofs tal-lemin, għaliex dan jiġri jikkonsisti minn tliet elementi. 

U hekk jien ser ngħid li l- nofs tax-xellug tan-nofs tax-xellug l-array huwa biss l-element ħamsa. Ħames, li tkun element wieħed firxa, nafu kif sort. U għalhekk ħamsa huwa magħżul. Aħna biss se jiddikjara li. Huwa firxa element wieħed. 

Allura aħna issa stajt magħżula l nofs xellug tal-half-- xellug jew minflok, konna magħżula l nofs xellug tal-larinġ. Allura issa, sabiex jibqa kompluta nofs xellugi tal-firxa globali tal- għandna bżonn biex issolvi l-nofs tal-lemin tal-larinġ, jew dan il-għalf. Kif nistgħu nagħmlu dan? Well, aħna għandna firxa tnejn element. Allura nistgħu sort l-nofs xellug mill-firxa, li huwa tnejn. Żewġ huwa element wieħed. Allura huwa magħżula fil-kontumaċja. Imbagħad nistgħu sort in-nofs lemini ta 'dak il-porzjon ta' l-array, il-wieħed. C'est tip ta 'kontumaċja. 

Dan issa huwa l-ewwel darba konna laħaq pass jingħaqdu. Aħna lestew, għalkemm aħna qed issa tip ta 'nested down-- u li tip ta 'l-delikata ħaġa ma recursion huwa, għandek bżonn biex iżommu tiegħek ras dwar fejn ninsabu. Allura aħna ħadthom tip ta 'ix-xellug nofs tal-porzjon oranġjo. 

U issa, aħna qed fin-nofs ta issortjar in-nofs lemini tal-porzjon oranġjo. U f'dak il-proċess, aħna issa waslu biex tkun fuq il-pass, jingħaqdu l-żewġ nofsijiet flimkien. Meta nħarsu lejn l-żewġ nofsijiet mill-firxa, naraw tnejn u wieħed. Li element huwa iżgħar? One. 

Imbagħad liema element huwa iżgħar? Ukoll, huwa tnejn jew xejn. Allura huwa tnejn. Allura issa, biss biex għal darb'oħra jinkwadra fejn ninsabu fil-kuntest, għandna magħżula l nofs xellug tal-larinġ u l-nofs tal-lemin tal-oriġini. Naf stajt biddel il-kuluri ġdid, iżda li meta konna. U r-raġuni I ma 'dan għaliex dan il-proċess huwa se jibqgħu għaddejjin, mtennija isfel. Imxejna magħżula ix-xellug nofs tal-ewwel oranġjo u l-nofs tal-lemin tal-ewwel oranġjo. 

Issa, għandna bżonn li jingħaqdu dawk żewġ nofsijiet flimkien wisq. Dik hija l-pass aħna qed fuq. Allura aħna nikkunsidraw kollha tal- elementi li issa huma ħodor, in-nofs tax-xellug tal-firxa oriġinali. U aħna jingħaqdu dawk jużaw l-istess proċess għamilna għal għaqda ta 'żewġ u wieħed ftit mument ilu. 

Il-half xellug,-iżgħar element fuq in-nofs tax-xellug huwa ħamsa. L-iżgħar element fuq in-nofs lemini huwa wieħed. Liema minn dawn huwa iżgħar? One. 

L-iżgħar element fuq in-nofs tax-xellug huwa ħamsa. L-iżgħar element fuq in-nofs lemini huwa tnejn. X'hemm-iżgħar? Tnejn. U mbagħad fl-aħħar ħames snin u xejn, nistgħu ngħidu ħamsa. 

OK, stampa daqshekk kbira, ejja jieħu pawża għat-tieni u ċifra barra fejn ninsabu. Jekk bdejna minn -bidu nett, aħna issa lestew għal l-array ġenerali biss pass wieħed mill-kodiċi pseudocode hawn. Aħna magħżula l- nofs xellug tal-firxa. 

Ifakkar li l-oriġinali ordni kien ta 'ħames, tnejn, li waħda. Billi jmorru permezz ta 'dan il-proċess u jbejtu isfel u jirrepeti, tkompli jiksru l-problema isfel f'partijiet iżgħar, aħna issa lestew pass wieħed mill-pseudocode għall-firxa sħiħa ta 'tluq. Aħna magħżula nofs xellugi tagħha. 

Allura issa ejja friża hemmhekk. U issa ejja sort-dritt nofs il-firxa oriġinali. U aħna qed tmur biex tagħmel dan billi għaddejjin mill-istess iterattiv proċess tat-tkissir affarijiet isfel u mbagħad jgħaqqadhom flimkien. 

Allura l-nofs tax-xellug tal- aħmar, jew il-half xellug tad-nofs tal-lemin tal-oriġinal firxa, jien ser ngħid huwa tlieta. Għal darb'oħra, jien qed konsistenti hawn. Jekk għandek fard numru ta 'elementi, huwa ma verament kwistjoni jekk inti tagħmel l-waħda xellug iżgħar jew id-dritt wieħed iżgħar. 

Li huwa importanti huwa li kull meta inti jiltaqgħu din il-problema fit-twettiq jingħaqdu, inti jeħtieġ li tkun konsistenti. Inti jew dejjem jeħtieġ li jagħmlu ġenb xellug iżgħar jew dejjem bżonn tagħmel il-lemin iżgħar. Hawnhekk, stajt għażlu li dejjem jagħmlu fuq ix-xellug iżgħar meta array tiegħi, jew tiegħi sub-firxa, huwa ta 'daqs fard. 

Tliet huwa element wieħed, u għalhekk huwa magħżul. Imxejna leveraged din il-preżunzjoni matul proċess kollu tagħna s'issa. Allura issa ejja sort-dritt nofs il-nofs tal-lemin, jew in-nofs lemini tal-aħmar. 

Għal darb'oħra, għandna bżonn li jaqsam din isfel. Din mhix firxa element wieħed. Ma nistgħux tiddikjaraha magħżula. U hekk l-ewwel, aħna qed tmur biex isolvi l-nofs tax-xellug. 

Il-half xellug huwa element wieħed, dan huwa tip ta 'kontumaċja. Allura aħna qed tmur biex issolvi d-dritt nofs, li hija element wieħed. Huwa magħżula fil-kontumaċja. U issa, nistgħu jingħaqdu dawn iż-żewġ flimkien. Erba hija iżgħar, u allura sitt hija iżgħar. 

Għal darb'oħra, X'għamilna f'dan il-punt? Imxejna magħżula ix-xellug nofs il-nofs tal-lemin. Jew li jmorru lura għall-oriġinali kuluri li kienu hemm, konna magħżula ix-xellug nofs il-aħmar artab. Din kienet oriġinarjament brick dlam aħmar u issa huwa aħmar artab, jew kien aħmar artab. 

U allura konna magħżula l nofs tal-lemin tal-aħmar artab. Issa, ukoll, dawn qed aħdar darb'oħra, biss għaliex aħna qed għaddejjin minn proċess. U aħna għandna jirrepetu dan aktar u aktar. 

Allura issa nistgħu jingħaqdu dawk żewġ nofsijiet flimkien. U dan huwa dak li nagħmlu hawn. Allura l-linja sewda ftit qasmet il-half xellug u l-nofs tal-lemin ta 'din il-parti tip. 

Inqabblu l-iżgħar valur fuq in-naħa tax-xellug tal-array-- jew skuża me,-iżgħar valur ta 'nofs tax-xellug għall-iżgħar valur tad-dritt nofs u ssib li tliet huwa iżgħar. U issa daqsxejn ta 'ottimizzazzjoni, id-dritt? Hemm fil-fatt xejn jitħalla fuq il-linja xellugija. 

M'hemm xejn li jifdal fuq in-naħa tax-xellug, sabiex inkunu nistgħu b'mod effiċjenti biss move-- nistgħu jiddikjaraw il-bqija ta 'dan huwa fil-fatt magħżula u biss tindi dan fuq, għaliex hemm xejn ieħor li qabbel kontra. U nafu li l-lemin tal-lemin huwa magħżul. 

OK, hekk issa ejja friża mill-ġdid u figura fejn ninsabu fl-istorja. Fil-firxa globali, dak li aħna jitwettqu? Imxejna attwalment twettaq issa passi wieħed u żewġ stadji. Aħna magħżula l-nofs tax-xellug, u aħna magħżula in-nofs lemini. 

Allura issa, dak kollu li jibqa 'huwa għalina li jingħaqdu dawn iż-żewġ nofsijiet flimkien. Allura aħna jqabblu l-aktar baxx vvalutati element ta 'kull nofs tas-firxa imbagħad u tipproċedi. Wieħed huwa inqas minn tlieta, hekk wieħed imur. 

Tnejn huwa inqas minn tlieta, hekk tnejn tmur. Tliet huwa inqas minn 5, hekk tlieta tmur. Erba huwa inqas minn 5, hekk erbgħa tmur. Imbagħad ħamsa inqas minn sitta, u sitta huwa dak kollu li jibqa '. 

Issa, naf, li kien ħafna ta 'passi. U konna xellug ħafna tal-memorja fl-eventwalità tagħna. U dan huwa dak dawk kwadri griż huma. U probabbilment qisni li ħa ħafna itwal minn tip inserzjoni, bubble sort, jew tip ta 'għażla. 

Imma attwalment, minħabba lott ta 'dawn il-proċessi qed jiġri fl-istess time-- li hija xi ħaġa aħna ser, għal darb'oħra, jitkellmu dwar meta nitkellmu dwar recursion fil-futur video-- dan algoritmu fil-fatt huwa ċar fundamentalment differenti minn kull ħaġa oħra rajna qabel iżda huwa wkoll ferm aktar effiċjenti. 

Għaliex huwa li? Ukoll, fl-agħar xenarju, għandna li jaqsam n elementi up u mbagħad Begonia minnhom. Iżda meta aħna recombine minnhom, dak li aħna qed tagħmel hija bażikament irduppjar tal- daqs tal-arrays iżgħar. Għandna mazz ta 'element wieħed arrays li aħna effettivament jikkombinaw f'żewġ arrays element. U allura nieħdu dawk żewġ arrays element u għaqqadhom flimkien fis erba arrays element, u l-bqija, u l-bqija, u fuq hekk, sakemm aħna jkollhom waħda firxa element n. 

Imma kemm doublings ma jieħdu biex jiksbu l n? Think lura għall-eżempju ktieb tat-telefon. Kif ħafna drabi ma rridu tiċrita il-ktieb tat-telefon fil nofs, kemm aktar drabi ma għandna biex tiċrita-ktieb tat-telefon fil nofs, jekk id-daqs tal-ktieb tat-telefon rdoppja? Hemm biss wieħed, id-dritt? 

Allura hemm xi tip ta ' element logaritmika hawn. Iżda aħna wkoll għad iridu mill-inqas tħares lejn l-elementi kollha n. Għalhekk fl-agħar każ, jingħaqdu sort tmur fil log n n. Irridu nħarsu lejn l-elementi kollha N, u għandna li jingħaqdu flimkien log n settijiet ta 'passi. Fil-xenarju aħjar, l-array huwa perfettament riżolta. Li l-kbir. Iżda bbażata fuq l-algoritmu għandna hawnhekk, aħna xorta jkollhom li jaqsam u Begonia. Għalkemm f'dan il-każ, il- jiżżewweġ huwa tip ta ineffettiv. Mhuwiex meħtieġ. Iżda aħna xorta jgħaddu il-proċess kollu xorta waħda. 

Hekk fil-każ aħjar u fl-agħar każ, dan algoritmu tmur fil log n n żmien. Jingħaqdu tip huwa definittivament daqsxejn delikati mill-algoritmi oħra issortjar ewlenin konna tkellimna dwar CS50 iżda sostanzjalment aktar qawwija. 

U hekk jekk inti qatt issib okkażjoni biex bżonnha jew jużah biex issolvi l- sett ta 'dejta kbar, jkollna ras tiegħek madwar l-idea ta 'recursion se tkun verament b'saħħtu. U li għaddej biex jagħmlu tiegħek programmi verament ħafna aktar effiċjenti użu jingħaqdu sort versus kull ħaġ'oħra. Jien Doug Lloyd. Dan huwa CS50.