>> [Daqq tal-mużika]
Doug LLOYD: Kull dritt, hekk sort bużżieqa huwa algoritmu
inti tista 'tuża biex issolvi sett ta' elementi.
Ejja tagħti ħarsa lejn kif taħdem.
>> Allura l-idea bażika wara sort bużżieqa hija din.
Aħna ġeneralment jridux jimxu ogħla elementi vvalutati ġeneralment fuq il-lemin,
u t'isfel elementi vvalutati ġeneralment lejn ix-xellug, kif nistgħu nistennew.
Aħna rridu l-affarijiet aktar baxxi li tkun fil il-bidu, u l-affarijiet ogħla
li jkun fl-aħħar.
>> Kif nistgħu nagħmlu dan?
Ukoll fil-kodiċi pseudocode, nistgħu ngħidu, ejja
tistabbilixxi counter swap għal valur mhux żero.
Ser naraw għaliex aħna tagħmel dan fit-tieni.
U allura aħna irrepeti ġej proċess sakemm il-counter tpartit huwa ta '0,
jew sakemm nagħmlu ebda swaps fil-livelli kollha.
>> Irrisettja l-counter tpartit biex 0 jekk ma jkunx diġà 0.
Imbagħad tħares lejn kull par biswit ta 'elementi.
Jekk dawn iż-żewġ elementi huma mhux biex, tpartit minnhom,
żid minn 1 sa l-counter tpartit.
Jekk int taħseb dwar dan qabel ma Ħares,
avviż li din se timxi aktar baxx elementi vvalutati lejn ix-xellug
u elementi għad-dritt ogħla vvalutati, effettivament tagħmel dak li rridu nagħmlu,
li hija timxi dawk il-gruppi ta 'elementi fil-mod.
Ejja Ħares kif dan tista 'tidher bl-użu firxa tagħna
li aħna użati biex jittestjaw dawn algoritmi.
Għandna firxa mhux magħżul hawn ukoll, indikat mill-elementi kollha
jkunu bl-aħmar.
U I sett swap counter tiegħi għal valur nonzero.
I għażlet arbitrarjament negattiv 1-- mhuwiex 0.
Nixtiequ ntennu dan il-proċess sakemm il-counter tpartit huwa ta '0.
Dan huwa għaliex I sett tpartit tiegħi kontra xi valur mhux żero,
għax inkella l- counter tpartit tkun 0.
Aħna lanqas biss tibda l- proċess ta 'l-algoritmu.
Għalhekk għal darb'oħra, il-passi are-- reset-counter tpartit
għal 0, imbagħad tħares lejn kull biswit par, u jekk dawn qed out of order,
tpartit lilhom, u żid 1 lejn il-counter tpartit.
Mela ejja tibda dan il-proċess.
Allura l-ewwel ħaġa li nagħmlu huwa aħna waqqafna l-counter tpartit għal 0,
u mbagħad nibdew infittxu f'kull par biswit.
>> Allura aħna ewwel tibda tħares lejn 5 u 2.
Naraw li jkunu barra mill- ordni u hekk aħna tpartit lilhom.
U aħna żid 1 lill-counter tpartit.
Allura issa counter swap tagħna huwa 1, u 2 u 5 ma jkunux mixgħula.
Issa aħna irrepeti l-proċess mill-ġdid.
>> Aħna nħarsu lejn l-par biswit jmiss, 5 u 1-- dawn qed wkoll out of order,
hekk aħna tpartit lilhom u żid 1 għall-kontro tpartit.
Imbagħad aħna nħarsu lejn 5 u 3.
Huma out of order, hekk aħna tpartit minnhom u aħna żid 1 lejn il-counter tpartit.
Imbagħad aħna nħarsu lejn 5 u 6.
Huma qed sabiex, hekk aħna ma attwalment jeħtieġ li tpartit xejn f'dan il-ħin.
Imbagħad aħna nħarsu lejn 6 u 4.
Huma wkoll qed out of order, hekk aħna tpartit minnhom u aħna żid 1 lejn il-counter tpartit.
>> Issa avviż dak li ġara.
Imxejna mċaqalqa 6-triq kollha sa l-aħħar.
Għalhekk fl sort għażla, jekk inti stajt jidher li video, dak li għamilna kien
aħna spiċċajna jiċċaqalqu l- Elementi iżgħar fil-bini
l-array Issortjati essenzjalment minn xellug għal-lemin, iżgħar għall-akbar.
Fil-każ ta 'tip bużżieqa, jekk aħna qed wara dan algoritmu partikolari,
aħna qed attwalment għaddejjin li tkun bini l-array magħżula mill lemin
għax-xellug, l-akbar għall-iżgħar.
Aħna effettivament effervexxentement 6, il- akbar valur, it-triq kollha sa l-aħħar.
>> U hekk aħna issa jistgħu jiddikjaraw li din hija magħżula,
u fil-futur iterations-- għaddejjin mill-firxa again--
aħna ma jkollhomx biex 6 aktar.
Aħna biss għandek tikkunsidra l-elementi mhux magħżul
meta aħna qed tħares lejn pari li jmissu magħhom.
Allura aħna lesti waħda jgħaddu sort bużżieqa.
Allura issa immorru lura għall-mistoqsija, irrepeti sakemm il-counter tpartit huwa ta '0.
Ukoll l-counter tpartit huwa ta '4, hekk aħna qed tmur
biex iżommu tirrepeti dan il-proċess mill-ġdid.
>> Aħna ser reset-counter tpartit għal 0, u ħarsa lejn kull par biswit.
Allura nibdew il 2 u 1-- dawn qed out of order, hekk aħna tpartit lilhom
u aħna żid 1 lejn il-counter tpartit.
2 u 3, li qed fl-ordni.
Aħna ma bżonn li tagħmel xejn.
3 u 5 huma fl-ordni.
Aħna ma bżonn li tagħmel xejn hemmhekk.
>> 5 u 4, jkunu barra ta 'ordni, u hekk aħna
jeħtieġ li tpartit lilhom u żid 1 għall-kontro tpartit.
U issa konna mċaqalqa 5, l-akbar element li jmiss,
sa l-aħħar tal-porzjon mhux magħżul.
Allura aħna issa jistgħu jċemplu li parti tal-porzjon magħżula.
>> Issa inti qed tħares lejn il- screen u probabbilment tista 'tgħid,
kif jista I, li l-firxa huwa magħżul dritt issa.
Iżda aħna ma jistax jipprova li għadu.
Aħna ma jkollhom garanzija li huwa magħżula.
Iżda din hija fejn l-iswap counter għaddej biex tidħol fin-nofs.
>> Allura aħna ve kompletati pass.
Il-counter tpartit huwa 2.
Allura aħna qed tmur biex jirrepeti dan il-proċess mill-ġdid,
irrepeti sakemm il-counter tpartit huwa ta '0.
Irrisettja l-counter tpartit għal 0.
Allura aħna ser reset.
>> Issa tħares lejn kull par biswit.
Li fl-ordni, 1 u 2.
2 u 3 huma fl-ordni.
3 u 4 huma fl-ordni.
Allura f'dan il-punt, l-avviż konna kompletati tħares lejn kull par biswit,
iżda l-counter tpartit għadu 0.
>> Jekk aħna ma jkollhom jaqilbu kull element, allura dawn
Jeħtiġilhom ikunu, minn saħħa ta 'dan il-proċess.
U għalhekk effiċjenza ta 'tipi, li xjenzjati we kompjuter imħabba,
huwa issa tista 'tiddikjara l-array kollu għandu
jiġu magħżula, għaliex aħna ma għandek tpartit xi elementi.
Li pretty sbieħ.
>> Allura x'inhu l-agħar każ xenarju bi sort bużżieqa?
Fl-agħar każ li l-firxa hija sabiex kompletament reverse,
u hekk aħna li bużżieqa kull mill-elementi kbar kollha
il-mod madwar l-firxa.
U aħna effettivament għandhom ukoll bużżieqa l-elementi kollha żgħar lura
it-triq kollha madwar l-firxa, wisq.
Allura kull wieħed mill-elementi n trid timxi firxa kollha tas-elementi l-oħra n.
Allura dak l-agħar każ.
Fl-aħjar każ xenarju għalkemm, dan huwa
kemmxejn differenti minn tip selezzjoni.
Il-firxa hija diġà magħżula meta immorru fil.
Aħna ma jkollhom jagħmlu xi swaps fuq l-ewwel pass.
Allura nistgħu nħarsu fil inqas l-elementi, id-dritt?
Aħna ma jkollhom jirrepetu dan jipproċessaw numru ta 'drabi matul.
>> Allura dak li jfisser?
Allura x'inhu l-agħar każ għall sort bużżieqa, u x'hemm
l aħjar każ għall tip bużżieqa?
Ridt raden dan?
Fl-agħar każ inti għandek jtenni madwar l-elementi kollha n n darbiet.
Allura l-agħar każ hija n kwadrat.
>> Jekk il-firxa hija perfettament Issortjati għalkemm, inti biss
għandek tfittex lejn kull mill-elementi darba.
U jekk il-counter tpartit għadu 0, inti tista 'tgħid dan array huwa magħżul.
U għalhekk fl-aħjar każ, dan huwa attwalment aħjar minn għażla
sort-- huwa omega ta n.
>> Jien Doug Lloyd.
Dan huwa CS50.