[Powered by Google Translate] [Sort Inserzjoni] [Tommy MacWilliam] [Università ta 'Harvard] [Dan huwa CS50.TV] Ejja tagħti ħarsa lejn it-tip inserzjoni, algoriżmu għat-teħid ta 'lista ta' numri u l-għażla tagħhom. Algoritmu, ftakar, huwa sempliċement proċedura ta 'pass pass għall-kisba ta' kompitu. L-idea bażika wara sort inserzjoni, huwa li jaqsam lista tagħna f'żewġ porzjonijiet, porzjon magħżula u porzjon mhux magħżul. 

F'kull pass ta 'l-algoritmu, numru jiġi mċaqlaq mill-porzjon mhux magħżul għall-porzjon magħżul sakemm eventwalment l-lista sħiħa huwa magħżul. Hawn hi l-lista ta 'sitt numri mhux magħżul - 23, 42, 4, 16, 8, u 15. Peress li dawn in-numri mhumiex kollha f'ordni axxendenti, dawn qed jintbagħtu f'volumi kbar. Minħabba li aħna ma bdew issortjar għadhom, aħna ser jikkunsidraw l-elementi kollha 6 porzjon mhux magħżul tagħna. 

Ladarba nibdew issortjar, aħna ser tpoġġi dawn in-numri magħżula fuq ix-xellug ta 'dawn. Allura, ejja tibda bil 23, l-ewwel element fil-lista tagħna. Aħna ma jkollu l-ebda elementi fil-porzjon magħżul tagħna għadhom, hekk ejja sempliċement jikkunsidraw 23 tkun il-bidu u t-tmiem tal-porzjon magħżul tagħna. Issa, porzjon magħżula tagħna numru wieħed, 23, u l-porzjon mhux magħżul tagħna dawn in-numri 5. Ejja issa daħħal in-numru li jmiss fil-porzjon mhux magħżul tagħna, 42, fis-porzjon magħżula. 

Biex tagħmel dan, aħna ser bżonn li jqabblu l-42 sa l-23 - l-uniku element fil-porzjon magħżul tagħna s'issa. Tnejn u erbgħin hija akbar minn 23, sabiex inkunu nistgħu sempliċiment jehmeż 42 sa l-aħħar tal-porzjon magħżul tal-lista. Great! Issa porzjon magħżula tagħna għandha żewġ elementi, u porzjon mhux magħżul tagħna għandha erba 'elementi. Allura, ejja issa jimxu lejn il-4, l-element li jmiss fil-porzjon mhux magħżul. Għalhekk, fejn għandhom dan jitpoġġa fil-porzjon magħżula? 

Ftakar, irridu li tqiegħed dan in-numru sabiex magħżula hekk porzjon magħżula tagħna jibqa korrett magħżula fil-ħinijiet kollha. Jekk aħna post-4 għad-dritt ta 'l-42, allura lista tagħna se jkun out of order. Allura, ejja tkompli miexja lemin għax-xellug fil-porzjon sort tagħna. Hekk kif nersqu, ejja shift kull numru isfel post biex tagħmel spazju għall-numru ġdid. Okay, 4 huwa wkoll anqas minn 23, hekk aħna ma tista 'poġġih lanqas hawn. Ejja jċaqalqu l-23 dritt f'post wieħed. 

Dan ifisser aħna tixtieq li post l-4 fl-islott ewwel fil-porzjon magħżula. Avviż kif dan l-ispazju fil-lista kienet diġà vojta, għaliex aħna kont qed jiċċaqilqu elementi magħżula isfel kif konna jiltaqgħu magħhom minnhom. Kull dritt. Allura, aħna qed nofs hemm. Ejja tkompli algoritmu tagħna billi ddaħħal il-16 fil-porzjon magħżula. Sittax huwa inqas minn 42, hekk ejja ċċaqlaq il-42 lejn il-lemin. Sittax huwa wkoll anqas minn 23, hekk ejja wkoll bidla dak l-element. 

Issa, 16 hija akbar minn 4. Għalhekk, jidher qisu aħna tixtieq li daħħal il-16 bejn l-4 u l-23. Filwaqt li jiċċaqilqu permezz tal-porzjon magħżula tal-lista mill-lemin għax-xellug, 4 hija l-ewwel numru Rajna li huwa iżgħar min-numru aħna qed tipprova li daħħal. Allura, issa nistgħu daħħal il-16 fil dan slot vojta, li, ftakar, aħna ve maħluqa mill-elementi li jiċċaqalqu fil-porzjon xorta fuq kif konna jiltaqgħu magħhom minnhom. 

Kull dritt. Issa, għandna erba 'elementi magħżula u żewġ elementi mhux magħżul. Allura, ejja jimxu l-8 fil-porzjon magħżula. Tmien huwa inqas minn 42. Tmien huwa inqas minn 23. U 8 hija inqas minn 16. Imma 8 hija akbar minn 4. Allura, aħna tixtieq li daħħal l-8 bejn l-4 u l-16. U issa aħna biss għandhom element wieħed aktar xellug biex issolvi - l-15. Ħmistax huwa inqas minn 42, Ħmistax huwa inqas minn 23. U 15 hija anqas minn 16. Iżda 15 hija akbar minn 8. 

Allura, hawn huwa fejn irridu li jagħmlu inserzjoni finali tagħna. U aħna qed isir. Għandna l-ebda elementi aktar fil-porzjon mhux magħżul, u l-porzjon magħżula tagħna huwa fl-ordni korretta. In-numri huma ordnati mill-iżgħar sa l-akbar. Allura, ejja tagħti ħarsa lejn uħud pseudocode li jiddeskrivi l-passi aħna biss mwettqa. 

Fl-linja 1, nistgħu naraw li għandna bzonn biex jtenni fuq kull element fil-lista ħlief l-ewwel, peress li l-ewwel element fil-porzjon mhux magħżul sempliċiment se jsiru l-ewwel element fil-porzjon magħżula. Fuq linji 2 u 3, aħna qed iżżomm rekord tal-post attwali tagħna fil-porzjon mhux magħżul. Element tirrapreżenta in-numru aħna bħalissa qed jiċċaqilqu fis-porzjon magħżula, u j tirrappreżenta indiċi tagħna fis-porzjon mhux magħżul. 

Fuq linja 4, aħna qed mtennija mill-parti magħżula mill-lemin għax-xellug. Aħna tixtieq li twaqqaf iterazzjoni ladarba l-element għall-xellug tal-pożizzjoni attwali tagħna huwa inqas mill-element aħna qed jippruvaw daħħal. Fuq linja 5, aħna qed tiċċaqlaq kull element niltaqgħu spazju wieħed lejn il-lemin. B'dan il-mod, aħna ser ikollhom spazju vojt li ddaħħal fil meta insibu l-ewwel element inqas mill-element aħna qed jiċċaqalqu. Fuq linja 6, aħna qed aġġornament counter tagħna biex tkompli timxi xellug ġol-parti magħżula. Fl-aħħarnett, fuq il-linja 7, aħna qed tiddaħħal l-element fil-porzjon magħżula tal-lista. 

Aħna nafu li huwa okay li ddaħħal fil-pożizzjoni j, għaliex konna diġà mxew l-element li jintuża biex tkun hemm spazju wieħed lejn il-lemin. Ftakar, aħna qed jiċċaqalqu permezz tal-porzjon magħżula mill-lemin għax-xellug, imma aħna qed jiċċaqilqu permezz tal-porzjon mhux magħżul mix-xellug għal-lemin. Kull dritt. Ejja issa tagħti ħarsa lejn kemm running ħa algoritmu li. Aħna ser ewwel titlob il-kwistjoni kemm żmien ma jieħdu għal dan algoritmu jiddekorri fl-agħar każ. Ifakkar li aħna jirrappreżentaw din id-darba t-tħaddim ma O notazzjoni Big. Sabiex issolvi lista tagħna, kellna biex jtenni fuq l-elementi fil-porzjon mhux magħżul, u għal kull wieħed minn dawk l-elementi, potenzjalment fuq l-elementi kollha fil-porzjon magħżula. Intuwittivament, dan ħsejjes bħal O (n ^ 2) operazzjoni. 

Ħarsa lejn pseudocode tagħna, aħna għandna loop nested ġewwa ieħor loop, li, fil-fatt, ħsejjes bħal O (n ^ 2) operazzjoni. Madankollu, il-porzjon magħżula ta 'lista ma tinkludi l-lista sħiħa sa l-aħħar ħafna. Still, nistgħu potenzjalment daħħal element ġdid fil-bidu nett tal-porzjon magħżul fuq kull iterazzjoni ta 'l-algoritmu, li jfisser li aħna'd nħarsu lejn kull element bħalissa fil-porzjon magħżula. Allura, li jfisser li għandna jistgħu potenzjalment jagħmlu waħda paragun għat-tieni element, 2 paraguni għat-tielet element, u l-bqija. Allura, in-numru totali ta 'passi hija s-somma ta' l-interi mill-1 għat-tul tal-lista minus 1. Nistgħu jirrappreżentaw dan bil-kalkolu totali. 

Aħna mhux se tidħol fis ammonti totali hawnhekk, iżda jirriżulta li din l-addizzjoni hija ugwali għal n (n - 1) aktar minn 2, li huwa n ekwivalenti ^ 2/2 - n / 2. Meta wieħed jitkellem dwar runtime asintotiku, din n ^ 2 terminu huwa ser jiddominaw dan it-terminu n. Allura, sort inserzjoni huwa Big O (n ^ 2). X'jiġri jekk aħna dam tip inklużjoni fil-lista diġà magħżula. F'dak il-każ, aħna'd sempliċiment jibnu l-porzjon magħżula mix-xellug għal-lemin. Allura, aħna ser bżonn biss fuq l-ordni ta 'passi n. 

Dan ifisser li tip inserzjoni għandu prestazzjoni aħjar każ ta 'ln, li nirrappreżentaw mal Ω (n). U li hija għal tip inserzjoni, biss wieħed mill-algoritmi ħafna nistgħu nużaw biex issolvi lista. Jisimni Tommy, u dan huwa CS50. [CS50.TV] Oh, inti biss ma tistax tieqaf li ladarba jibda. Oh, aħna ma li - Boom >>!