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