[Powered by Google Translate] [Bubble aina] [JACKSON STEINKAMP HARVARD UNIVERSITY] [HII NI CS50. CS50TV] Bubble Panga ni mfano wa algorithm kuchagua - kwamba ni, utaratibu kwa ajili ya kuchagua seti ya vipengele katika wakipanda au kushuka ili. Kwa mfano, kama alitaka kutatua safu yenye namba [3, 5, 2, 9], utekelezaji sahihi wa aina Bubble atarudi Iliyopangwa safu [2, 3, 5, 9] katika wakipanda ili. Sasa, mimi naenda kueleza katika pseudocode jinsi algorithm kazi. Hebu sema tuko kuchagua orodha ya integers 5-3, 2, 9, 6, na 5. algorithm kuanza kwa kuangalia mambo mawili ya kwanza, 3 na 2, na kuangalia kama uko nje ya utaratibu jamaa na kila mmoja. Wao ni - 3, ni mkubwa kuliko 2. Kuwa ili wakipanda, wanapaswa kuwa na njia nyingine kote. Hivyo, sisi byta yao. Sasa orodha inaonekana kama hii: [2, 3, 9, 6, 5]. Next, sisi kuangalia vipengele pili na wa tatu, 3 na 9. Wao ni katika mpangilio sahihi jamaa na kila mmoja. Hiyo ni, 3 ni chini ya 9 hivyo algorithm haina byta yao. Next, sisi kuangalia 9 na 6. Wao ni nje ya utaratibu. Hivyo, tunahitaji wabadilishane yao kwa sababu 9, ni mkubwa kuliko 6. Mwisho, sisi kuangalia integers miwili iliyopita, 9 na 5. Wao ni nje ya utaratibu, hivyo ni lazima swapped. Baada ya kwanza kupita kamili kupitia orodha, inaonekana kama hii: [2, 3, 6, 5, 9]. Si mbaya. Ni karibu Iliyopangwa. Lakini tunahitaji kukimbia kupitia orodha tena ya kupata hiyo kabisa Iliyopangwa. Mbili ni chini ya 3, hivyo hatuna byta yao. Tatu ni chini ya 6, hivyo hatuna byta yao. Sita, ni mkubwa kuliko 5. Sisi swapped. Sita ni chini ya 9. Hatuna wabadilishane. Baada ya kupita pili kupitia, inaonekana kama hii: [2, 3, 5, 6, 9]. Perfect. Sasa, hebu andika katika pseudocode. Kimsingi, kwa kila kipengele katika orodha, tunahitaji kuangalia ni na kipengele moja kwa moja na haki yake. Kama wao ni nje ya utaratibu jamaa na kila mmoja - yaani kama kipengele juu ya kushoto ni mkubwa kuliko mmoja kulia - tunapaswa wabadilishane mambo mawili. Sisi kufanya hili kwa kila kipengele cha orodha, na tumekuwa alifanya moja kupita. Sasa sisi tu kufanya kupitisha-kupitia mara ya kutosha kuhakikisha orodha kikamilifu, ipasavyo Iliyopangwa. Lakini mara ngapi Je, tuna kupita katika orodha ya kuthibitisha kwamba sisi ni kosa? Naam, hali mbaya zaidi kesi ni kama tuna orodha kabisa nyuma. Kisha inachukua idadi ya kupita throughs-sawa na idadi ya mambo ya n-1. Kama hii haina mantiki intuitively, kufikiri ya kesi rahisi - orodha [2, 1]. Hii ni kwenda kuchukua kupitisha moja-kwa njia ya kutatua usahihi. [3, 2, 1] - kesi mbaya zaidi ni kwamba pamoja na mambo 3 sorted nyuma, ni kwenda kuchukua iterations 2 kwa aina. Baada iteration moja, ni [2, 1, 3]. mavuno ya pili safu sorted [1, 2, 3]. Hivyo unajua kamwe kwenda kupitia safu, kwa ujumla, zaidi ya mara n-1, ambapo n ni idadi ya vipengele katika safu. Ni wito Bubble Panga kwa sababu vipengele kubwa huwa na 'Bubble-up' kwa haki pretty haraka. Kwa kweli, algorithm hii ina kuvutia sana tabia. Baada iterations m kupitia safu nzima, rightmost vipengele m uhakika sorted katika nafasi zao sahihi. Kama unataka hii kuona mwenyewe, tunaweza kujaribu katika orodha ya nyuma kabisa [9, 6, 5, 3, 2]. Baada ya kupitisha moja kwa njia ya orodha nzima, [Sauti ya kuandika] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] kipengele rightmost 9 ni katika nafasi yake sahihi. Baada ya pili kupitisha-kupitia, 6 itakuwa na 'bubbled-up' kwa pili rightmost mahali. mambo mawili juu ya haki - 6 na 9 - itakuwa katika maeneo yao sahihi baada ya kwanza mbili kupita-throughs. Hivyo, jinsi gani tunaweza kutumia hii optimize algorithm? Naam, baada ya mmoja iteration kupitia safu sisi si kweli haja ya kuangalia kipengele rightmost kwa sababu tunajua ni Iliyopangwa. Baada iterations mbili, tunaweza kujua kwa uhakika rightmost mawili muhimu ni katika mahali. Hivyo, kwa ujumla, baada ya k iterations kupitia safu kamili, kuangalia vipengele k mwisho ni redundant tangu tunajua wao uko katika eneo sahihi tayari. Hivyo kama wewe ni kuchagua safu ya vipengele n, juu ya iteration kwanza - you'll kuwa na kuchambua wote wa mambo - kwanza n-0. On iteration pili, itabidi kuangalia wote wa mambo lakini mwisho - kwanza n-1. Optimization mwingine inaweza kuwa kwa kuangalia kama orodha tayari sorted baada ya kila iteration. Kama ni tayari Iliyopangwa, hatuna haja ya kufanya iterations yoyote zaidi kupitia orodha. Tunawezaje kufanya hivyo? Naam, kama sisi hatuwezi kufanya swaps yoyote juu ya kupitisha-kwa njia ya orodha, ni wazi kuwa orodha tayari alikuwa Iliyopangwa kwa sababu hatukuwa wabadilishane chochote. Hivyo sisi dhahiri hawana kutatua tena. Pengine unaweza initialize variable bendera iitwayo 'si vyema' kwa uongo na kubadilisha kwa kweli kama una wabadilishane vipengele yoyote juu ya moja iteration kupitia safu. Au vile vile, kufanya kinyume na uhesabu swaps kufanya yoyote iteration aliyopewa. Wakati wa mwisho wa iteration, ikiwa hakuwa wabadilishane yoyote ya vipengele, unajua orodha tayari sorted na wewe ni kosa. Bubble Panga, kama algorithms nyingine kuchagua, unaweza kuwa tweaked kufanya kazi kwa ajili ya mambo yoyote ambayo yana njia kuagiza. Hiyo ni, kutokana na mambo mawili muhimu una njia kusema kama moja ya kwanza ni mkubwa kuliko, sawa au chini ya pili. Kwa mfano, unaweza kutatua wa alfabeti kwa kusema kwamba