[Music kucheza] DOUG LLOYD: zote haki, hivyo Bubble aina ni algorithm unaweza kutumia aina seti ya vipengele. Hebu tuangalie jinsi kazi. 

Hivyo wazo la msingi la Bubble aina ni hii. Sisi kwa ujumla wanataka kuhamia juu mambo yenye thamani ujumla na haki, na kupunguza mambo yenye thamani ujumla kwa upande wa kushoto, kama sisi bila kutarajia. Tunataka mambo ya chini kwa kuwa katika mwanzo, na mambo ya juu kuwa mwishoni. 

Je, sisi kufanya hivyo? Vizuri katika pseudocode kificho, tunaweza kusema, hebu kuweka wabadilishane kinyume na thamani mashirika yasiyo ya sifuri. Tutaweza kuona nini sisi kufanya hivyo katika pili. Na kisha sisi kurudia zifuatazo mchakato mpaka wabadilishane kukabiliana ni 0, au mpaka sisi kufanya hakuna swaps hata kidogo. 

Rudisha wabadilishane kinyume na 0 kama si tayari 0. Kisha kuangalia kila karibu jozi ya vipengele. Kama mambo hayo mawili ni si ili, wabadilishane yao, na kuongeza 1 kwa wabadilishane kukabiliana. Kama wewe ni kufikiri kuhusu hii kabla ya taswira yake, taarifa kwamba hii itakuwa hoja chini mambo yenye thamani kwa upande wa kushoto na ya juu yenye thamani ya vipengele na haki, ufanisi kufanya nini tunataka kufanya, ambayo ni kusonga makundi hayo ya mambo katika njia hiyo. Hebu taswira jinsi hii ili kuangalia kwa kutumia safu yetu kwamba sisi kutumika kwa mtihani nje algorithms haya. Tuna safu zisizochambuliwa hapa tena, unahitajika kwa wote wa mambo kuwa katika nyekundu. Na mimi kuweka wabadilishane yangu ya kukabiliana na kwa thamani nonzero. Mimi kiholela alichagua hasi 1-- siyo 0. Tunataka kurudia utaratibu huu mpaka wabadilishane kukabiliana ni 0. Hii ni kwa nini mimi kuweka wabadilishane yangu kinyume na baadhi thamani mashirika yasiyo ya sifuri, kwa sababu vinginevyo wabadilishane kukabiliana itakuwa 0. Tunataka hata kuanza mchakato wa algorithm. Hivyo tena, hatua are-- upya wabadilishane kukabiliana 0, kisha kuangalia kila karibu jozi, na kama uko nje ya utaratibu, wabadilishane yao, na kuongeza 1 kwa wabadilishane kukabiliana. Basi hebu kuanza mchakato huu. Hivyo jambo la kwanza sisi kufanya ni sisi kuweka wabadilishane kinyume na 0, na kisha sisi kuanza kuangalia katika kila jozi karibu. 

Hivyo sisi kwanza kuanza kuangalia 5 na 2. Tunaona kwamba wao ni nje ya ili na hivyo sisi kubadilishana nao. Na sisi kuongeza 1 kwa wabadilishane kukabiliana. Hivyo sasa wabadilishane yetu ya kukabiliana na ni 1, na 2 na 5 wamekuwa kimewashwa. Sasa sisi kurudia utaratibu tena. 

Sisi kuangalia ijayo jozi karibu, 5 na 1-- wao uko pia nje ya utaratibu, hivyo sisi wabadilishane yao na kuongeza 1 kwa wabadilishane kukabiliana. Kisha sisi kuangalia 5 na 3. Wao ni nje ya utaratibu, hivyo sisi wabadilishane wao na sisi kuongeza 1 kwa wabadilishane kukabiliana. Kisha sisi kuangalia 5 na 6. Wao ni ili, hivyo sisi si kweli haja wabadilishane chochote wakati huu. Kisha sisi kuangalia 6 na 4. Wao ni pia nje ya utaratibu, hivyo sisi wabadilishane wao na sisi kuongeza 1 kwa wabadilishane kukabiliana. 

Sasa angalia nini kilichotokea. Tumekuwa wakiongozwa 6 njia yote hadi mwisho. Hivyo katika uteuzi aina, kama wameweza kuonekana kwamba video, tulichokifanya ni sisi kuishia kusonga mambo madogo katika jengo safu Iliyopangwa kimsingi kutoka kushoto na kulia, wadogo na ukubwa. Katika kesi ya Bubble aina, kama tuko kufuatia algorithm hii hasa, sisi ni kweli kwenda kuwa jengo safu Iliyopangwa kutoka kulia kwa upande wa kushoto, kubwa na ndogo. Tuna ufanisi bubbled 6, thamani kubwa, njia yote hadi mwisho. 

Na ili tuweze sasa kutangaza kuwa kwamba ni yamepangwa, na katika siku zijazo iterations-- kwenda kwa safu again-- hatuna kuzingatia 6 tena. Sisi tu kuwa na kufikiria mambo zisizochambuliwa wakati sisi ni kuangalia jozi karibu. Hivyo tuna kumaliza moja kupita katika Bubble aina. Hivyo sasa sisi kurudi nyuma kwa swali, kurudia mpaka wabadilishane kukabiliana ni 0. Naam wabadilishane kukabiliana ni 4, hivyo tunakwenda kuweka kurudia utaratibu huu tena. 

Tunakwenda upya wabadilishane kukabiliana 0, na kuangalia kila jozi karibu. Hivyo sisi kuanza na 2 na 1-- wao uko nje ya utaratibu, hivyo sisi wabadilishane yao na sisi kuongeza 1 kwa wabadilishane kukabiliana. 2 na 3, wao uko katika utaratibu. Hatuna haja ya kufanya kitu chochote. 3 na 5 ni kwa utaratibu. Hatuna haja ya kufanya kitu chochote pale. 

5 na 4, wao ni nje ya utaratibu, na hivyo sisi haja wabadilishane yao na kuongeza 1 kwa wabadilishane kukabiliana. Na sasa tumekuwa wakiongozwa 5, ijayo kubwa kipengele, hadi mwisho wa fungu zisizochambuliwa. Ili tuweze sasa wito kwamba sehemu ya fungu yamepangwa. 

Sasa wewe ni kuangalia katika screen na pengine wanaweza kuwaambia, kama naweza, kwamba safu ni vyema hivi sasa. Lakini hatuwezi kuthibitisha kuwa bado. Hatuna uhakika kwamba ni vyema. Lakini hii ni mahali ambapo wabadilishane kukabiliana kinaendelea kuja katika kucheza. 

Hivyo tumekuwa kukamilika kupita. Wabadilishane kukabiliana ni 2. Hivyo sisi ni kwenda kurudia mchakato huu tena, kurudia mpaka wabadilishane kukabiliana ni 0. Rudisha wabadilishane kinyume na 0. Hivyo tutaweza upya. 

Sasa tuangalie kila jozi karibu. Hiyo ni kwa utaratibu, 1 na 2. 2 na 3 ni kwa utaratibu. 3 na 4 ni kwa utaratibu. Hivyo katika hatua hii, taarifa tumekuwa kukamilika kuangalia kila jozi karibu, lakini wabadilishane kukabiliana bado ni 0. 

Kama hatuwezi kuwa na kubadili mambo yoyote, basi wao lazima ili, na mujibu wa utaratibu huu. Na hivyo ufanisi wa kila aina, kwamba wanasayansi sisi kompyuta upendo, ni sasa tunaweza kutangaza safu nzima lazima kutatuliwa, kwa sababu hatukuwa na wabadilishane mambo yoyote. Hiyo ni pretty nzuri. 

Basi nini hali mbaya mazingira na Bubble aina? Katika hali mbaya zaidi safu ni ili reverse kabisa, na hivyo inabidi Bubble kila ya mambo makubwa zote njia hela safu. Na sisi kwa ufanisi pia kuwa na Bubble wote wa mambo madogo nyuma njia yote katika safu, pia. Hivyo kila moja ya mambo n ana hoja katika yote ya mambo mengine n. Hivyo hiyo ni mazingira ya kesi mbaya. Katika kesi bora mazingira ingawa, hii ni tofauti kidogo kutoka uteuzi aina. Safu tayari yamepangwa wakati sisi kwenda katika. Hatuna kufanya lolote swaps juu ya kupita kwanza. Hivyo tuwe na kuangalia katika mambo machache, sawa? Hatuna kurudia huu mchakato idadi ya nyakati juu. 

Hivyo nini maana gani? Basi nini mazingira ya kesi mbaya kwa Bubble aina, na nini bora kesi mazingira kwa Bubble aina? Je, nadhani hili? Katika hali mbaya zaidi una iterate hela zote mambo n n mara. Hivyo kesi mbaya ni n squared. 

Kama safu ni kikamilifu Iliyopangwa ingawa, wewe tu kuwa na kuangalia kila ya mambo mara moja. Na kama wabadilishane kukabiliana bado ni 0, unaweza kusema safu hii ni Iliyopangwa. Na hivyo katika kesi bora, hii ni kweli bora kuliko uteuzi sort-- ni omega ya n. 

Mimi nina Doug Lloyd. Hii ni CS50.