>> [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.