[Daqq tal-mużika] 

Doug LLOYD: Allura tip inserzjoni hija ieħor algoritmu nistgħu nużaw biex issolvi firxa. L-idea wara dan algoritmu huwa biex tinbena array Issortjat tiegħek fis-seħħ, elementi ċaqliq minn il-mod kif tmur, biex tagħmel spazju. Dan huwa kemmxejn differenti minn tip selezzjoni jew bżieżaq sort, per eżempju, fejn aħna qed jaġġusta l-postijiet, fejn aħna qed jagħmlu swaps. 

F'dan il-każ dak li aħna qed attwalment tagħmel huwa elementi li jiżżerżqu fuq, barra mill-mod. Kif jaħdem dan algoritmu jaħdmu pseudocode? Well ejja biss b'mod arbitrarju jgħidu li l- ewwel element tal-array huwa magħżul. Aħna qed tinbena fil-post. 

Aħna gonna jmorru element wieħed fi żmien u tinbena, u għalhekk l-ewwel ħaġa li naraw huwa firxa element wieħed. U bid-definizzjoni, wieħed element array huwa magħżul. 

Imbagħad aħna ser irrepeti dan il-proċess until-- aħna ser irrepeti l-proċess li ġej sakemm l-elementi kollha huma magħżula. Ħares lejn l-element mhux magħżul li jmiss u daħħalha fil-porzjon magħżula, billi ċċaqlaq-numru meħtieġ ta 'elementi barra mill-mod. Nisperaw li dan viżwalizzazzjoni se tgħinek tara eżattament x'hemm għaddej ma sort inserzjoni. 

Għalhekk għal darb'oħra, hawnhekk tagħna firxa mhux magħżul kollu, l-elementi kollha indikati bl-aħmar. U ejja isegwu l- passi ta 'pseudocode tagħna. L-ewwel ħaġa li għandna nagħmlu, huwa nsejħu l ewwel element tal-firxa, magħżula. Allura aħna qed biss jgħidu gonna ħames, int issa magħżula. 

Imbagħad aħna nħarsu lejn il-li jmiss element mhux magħżul mill-firxa u rridu biex jiddaħħal li fil-porzjon magħżula, billi ċċaqlaq elementi fuq. Allura tnejn huwa mhux magħżul li jmiss element tad-array. Ovvjament jappartjeni qabel l- ħames, hekk dak li aħna qed gonna do huwa tip ta 'istiva żewġ imwarrba għat-tieni, bidla ħamsa fuq, u mbagħad daħħal żewġ qabel ħames, fejn għandhom imorru. U issa nistgħu ngħidu li żewġ huwa magħżul. 

Allura kif tista 'tara, konna biss s'issa ħares lejn żewġ elementi tal-firxa. Aħna ma ħares lejn il- mistrieħ fil-livelli kollha, iżda konna ltqajna dawn iż-żewġ elementi magħżula mill mod tal-mekkaniżmu ċaqliq. 

Allura aħna irrepeti l-proċess mill-ġdid. Ħares lejn il-mhux magħżul li jmiss element, li wieħed. Ejja tiddeċiedi li twarrab għat-tieni, bidla kollox fuq, u mqiegħda wieħed fejn għandhom imorru. 

Għal darb'oħra, xorta, konna biss qatt ħares lejn wieħed, tnejn, u ħamsa. Ma nafux x'iktar huwa li ġejjin, imma konna magħżula dawk it-tliet elementi. 

Element mhux magħżul li jmiss huwa tlieta, hekk aħna ser dan għandu jiġi annullat. Aħna ser bidla fuq dak li aħna jeħtieġ li, din id-darba mhux kollox bħal fil-preċedenti żewġ każijiet, huwa biss l-ħames. U allura aħna ser twaħħal tlieta fil- bejn it-tnejn u l-ħames. 

Sitt huwa li jmiss mhux magħżul element lill-firxa. U fil-fatt sitt jkun iktar minn ħamsa, sabiex aħna lanqas biss bżonn tagħmel xi iskambji. Nistgħu biss tindi sitta dritt fuq l-aħħar tal-porzjon magħżula. 

Fl-aħħar nett, erba huwa l- aħħar element mhux magħżul. Allura aħna ser dan għandu jiġi annullat, bidla fuq l-elementi għandna bżonn li ċċaqlaq fuq, u mbagħad titqiegħed erba fejn jappartjeni. U issa nħarsu, konna sort ta 'l-elementi. Avviż bil inserzjoni sort, aħna ma kellhiex li jmorru quddiem u lura madwar l-firxa. Aħna biss marru madwar il-firxa żmien wieħed, u aħna qalbu affarijiet li aħna'd diġà ltaqgħu magħhom, sabiex biex tagħmel spazju għall-elementi ġodda. 

Allura x'inhu l-agħar każ xenarju bi sort inserzjoni? Fl-agħar każ, il- firxa hija fl-ordni reverse. Inti għandek li ċċaqlaq kull wieħed mill-elementi N sa pożizzjonijiet n, kull darba we wieħed jagħmlu inserzjoni. Li l-lott ta 'ċaqliq. 

Fl-aħjar każ, il- array huwa perfettament riżolta. U tip simili dak li ġara ma 'ħames u sitt fl-eżempju, fejn nistgħu biss tindi fuq mingħajr ma jkollhom jagħmlu xi ċaqliq, aħna'd essenzjalment tagħmel dan. 

Jekk inti jimmaġina li tagħna firxa kienet waħda permezz sitta, aħna'd tibda off billi tiddikjara wieħed huwa magħżul. Żewġ wasal wara waħda sabiex inkunu nistgħu biss jgħidu, OK, ukoll wieħed u tnejn huma magħżula. Tliet wasal wara żewġ hekk, OK, wieħed u tnejn u tlieta huma magħżula. 

Aħna ma tagħmel xi swaps, aħna qed biss jiċċaqalqu din il-linja arbitrarja bejn magħżula u mhux magħżula kif immorru. B'mod effettiv kemm għamilna fl-eżempju, tidwir elementi blu, kif aħna tipproċedi. Allura x'inhu l-runtime agħar każ, allura? Ftakar, jekk irridu bidla kull wieħed l-elementi n pożizzjonijiet n possibilment, nisperaw li jagħtik idea li l-agħar każ runtime huwa O Big ta n kwadrat. 

Jekk il-firxa hija perfettament magħżula, kollha għandna nagħmlu huwa tħares lejn kull element wieħed darba, u allura aħna qed isir. Allura fil-każ aħjar, huwa omega ta n. 

Jien Doug Lloyd. Dan huwa CS50.