[Powered by Google Translate] [Jingħaqdu Sort]
[Rob Bowden - Università ta 'Harvard]
[Dan huwa CS50. - CS50.TV]
Ejja nitkellmu dwar it-tip jingħaqdu.
S'issa inti stajt tidher tip bużżieqa, sort inserzjoni, u sort għażla.
Għalkemm I ser tip ta 'mewġa idejn tiegħi fil dak I jfisser minn aħjar,
jingħaqdu tip ġeneralment twettaq aħjar minn kwalunkwe minn dawn it-tipi 3.
>> Iżda qabel ma jitkellem dwar it-tip jingħaqdu, ejja nitkellmu dwar amalgamazzjoni 2 jelenka magħżula.
Aħna ser sejħa-proċess tat-teħid 2 jelenka magħżula, bħal dawn,
u jagħmlu lista unika mifthiema minnhom - li qed jingħaqdu l-listi.
Kif nistgħu nagħmlu dan?
Ukoll, wieħed idea hija li biss stick lista waħda fuq it-tmiem tal-lista l-oħra
u mbagħad sort l-lista li jirriżulta.
>> Filwaqt li dan jaħdem, huwa ħafna xogħol bla bżonn.
Nistgħu nagħmlu dan aktar malajr milli sempliċiment għażla.
Avviż li wieħed idea ħażina hija li ħu tazzi jalternaw minn kull lista.
Filwaqt li jista 'jidher li x-xogħlijiet fl-ewwel,
tagħmel li aħna jispiċċaw ma 4, 8, 15, 23, 16 - avviż li 16 u 23 huma barra mill-post.
Dan huwa minħabba 2 elementi li għandhom jidhru konsekuttiva fil-lista magħquda
huma fil-lista inizjali istess.
Kemm 15 u 16 huma fil-lista fuq ix-xellug.
Il-trick huwa li jieħdu vantaġġ mill-fatt li ż-żewġ listi huma diġà magħżula.
Dan ifisser li jekk aħna biss ħarsa lejn l-ewwel elementi taż-żewġ listi -
hawn, 4 u 8 - wieħed minnhom għandhom ukoll ikunu l-ewwel element tal-lista magħquda.
Ukoll, għaliex huwa li?
Dawn iż-żewġ listi huma diġà magħżula,
u dan jew 4 jew 8 irid ikun l-element iżgħar meta aħna ngħaqqdu l-listi 2.
F'dan il-każ, l-iżgħar huwa 4,
hekk nistgħu jieħdu out 4 u jagħmilha l-ewwel element tal-lista magħquda tagħna.
Issa aħna nkomplu li qed jingħaqdu l-bqija 3 elementi tal-ewwel lista
u 4 elementi tal-lista tat-tieni.
>> Għal darb'oħra, aħna biss bżonn li nħarsu lejn l-ewwel element ta 'żewġ listi.
L-iżgħar tal-2 għandha tkun it-tieni element tal-lista magħquda tagħna.
Din id-darba, bejn 8 u 15-iżgħar huwa 8, u hekk aħna daħħal li
bħala l-element tieni lista magħżula tagħna.
Nistgħu tkompli tqabbel l-ewwel elementi taż-żewġ listi
u tneħħi l-iżgħar ta 'l-2.
Tqabbil 15 u 23, 15 hija iżgħar u għalhekk dan huwa tielet element tagħna.
Issa jitqabblu 16 u 23, 16 hija iżgħar.
Allura dak l-element 4.
>> Avviż li 2 elementi ġew mill-istess lista fil-filliera.
Dan huwa għaliex il-lista magħquda ma tistax biss elementi supplenti mil-listi 2.
Tqabbil 50 u 23, 23 hija iżgħar, hekk aħna jagħżlu li.
Bejn 50 u 42, 42 hija iżgħar.
Bejn 50 u 108, 50 hija iżgħar.
U, finalment, aħna biss ikollhom 108, u għalhekk għandha timxi fuq l-aħħar tal-lista tagħna.
Avviż li għandna sbieħ, lista magħżula.
Kull darba qabbilna l-ewwel 2 elementi tal-listi 2
konna kapaċi li jiddeterminaw l-element li jmiss tal-lista magħquda.
Dan ifisser li jekk il-lista finali fih in-numri n, fejn n hija hawnhekk 8,
allura għandna bżonn fil-paraguni aktar n biex tikseb kollha ta 'dawn in-numri fil-post it-tajjeb.
Tali algoritmu huwa qal li jimxu fil-ħin lineari,
iżda ma joqogħdu jinkwetaw dwar li hawn.
>> Bl-użu algoritmu tagħna għall jingħaqdu, nistgħu nagħmlu l-algoritmu mgħaġġel sort jingħaqdu.
Allura, ejja reset listi tagħna.
Hemm 2 passi kbar fil-proċess ta 'tip jingħaqdu.
L-ewwel, kontinwament taqsam il-lista tal-cups fis nofsijiet
sakemm għandna mazz ta 'listi mal biss 1 tazza fihom.
Tinkwetax jekk lista fiha numru fard
u inti ma tistax tagħmel qatgħa perfettament nadif bejniethom.
Just pick arbitrarjament li lista biex tinkludi l-tazza żejda pulzieri
Allura, ejja maqsuma dawn il-listi.
Issa għandna 2 listi.
Issa għandna 4 listi.
>> U issa għandna 8 listi ma 'tazza waħda f'kull lista.
Allura dak li għall-pass 1.
Għal pass 2, aħna ripetutament jingħaqdu pari ta 'listi li jużaw l-algoritmu jingħaqdu aħna tgħallimna qabel.
Twaħħid 108 u 15, aħna jispiċċaw mal-lista 15, 108.
Twaħħid 50 u 4, aħna jispiċċaw ma '4, 50.
Twaħħid 8 u 42, aħna jispiċċaw bi 8, 42.
U qed jingħaqdu 23 u 16, aħna jispiċċaw ma 16, 23.
Issa listi kollha tagħna huma ta 'daqs 2.
Avviż li kull wieħed mill-listi 4 huwa magħżul.
>> Allura aħna tista 'tibda amalgamazzjoni pari ta' listi ġdid.
Twaħħid 15 u 108 u 4 u 50 -
1 jieħdu l-4, allura l-15, allura l-50, allura l-108.
Twaħħid 8, 42 u 16, 23,
aħna l-ewwel jieħu l-8, allura l-16, allura l-23, allura l-42.
Allura issa għandna biss 2 listi ta 'daqs 4, li kull wieħed minnhom huwa magħżul.
Allura issa aħna jingħaqdu dawn il-listi 2.
L-ewwel nieħdu l-4.
Imbagħad aħna jieħdu l-8.
Imbagħad nieħdu l-15 u 16, allura 23, imbagħad 42, imbagħad 50, imbagħad 108.
U aħna qed isir.
Issa għandna lista magħżula.
Allura kif fast kien dan, eżattament?
F'termini tekniċi, xorta jingħaqdu hija O (n log n),
billi kollha ta 'tip bużżieqa, sort inserzjoni, u sort l-għażla huma O (n ²).
Fil-fatt, kif inti ser jitgħallmu malajr, inti mhux se tkun kapaċi li toħroġ bi speċi
li jwettaq aħjar minn O (n log n) fil-każ ġenerali.
Għal darb'oħra, ma joqogħdu jinkwetaw dwar dan notazzjoni O kbir jekk inti ma bbenefikawx encore.
>> Biss jafu li dan ifisser li jekk ridna li sort lista verament kbir
sort bużżieqa, sort inserzjoni, u l-għażla sort potenzjalment jistgħu jieħdu
wisq itwal minn jingħaqdu tip.
Dan ma jfissirx li tip jingħaqdu se tkun iktar mgħaġġla għall-listi kollha
jew saħansitra għal xi lista waħdanija taħt ċertu daqs.
Per eżempju, it-tip inserzjoni tista 'tkun l-xorta aktar mgħaġġla għall-listi kollha iżgħar minn 5 elementi.
Fil-prattika, xorta jingħaqdu huwa normalment aktar mgħaġġel għal listi żgħira kemm 50 elementi.
>> Iżda din il-veloċità żejda ma jaqax mingħajr prezz.
B'differenza tipi oħra tagħna, li jieħu lista u timmodifika l-lista fil-post
sakemm aħna jiksbu lista magħżula, sort jingħaqdu teħtieġ xi spazju addizzjonali
biex jingħaqdu 2 telenka flimkien.
Aħna ma jistax immedjatament jużaw il-listi li qed jiġu amalgamati biex jaħżnu l-lista magħquda
peress li aħna jista 'jwarrab l-elementi li għad iridu jiġu amalgamati.
Dan l-ispazju huwa daqsxejn ta 'prezz, iżda normalment mhuwiex irraġonevoli.
U li hija għal tip jingħaqdu.
>> Jisimni Rob Bowden, u dan huwa CS50.
[CS50.TV]
- U l-għażla tip.
[Laughs]
Oh, ltqajna biex jieħdu dik fl wisq minħabba I switched kif I kien jippreżentah.
Lista ix-xellug. Dan kien typo.
[Misspoke] I invitat up -
[Laughs]
I do not know dak -