[MUSIC nagpe-play] DOUG LLOYD: Lahat ng mga karapatan, kaya bubble sort ay isang algorithm maaari mong gamitin upang ayusin ang isang hanay ng mga elemento. Tingnan natin ang isang pagtingin sa kung paano ito gumagana. 

Kaya ang pangunahing ideya sa likod bubble sort ay na ito. Karaniwan naming nais na ilipat ang mas mataas minamahal na mga elemento sa pangkalahatan sa kanan, at mas mababa ang mga mahal na mga elemento sa pangkalahatan sa kaliwa, tulad ng gagawin namin inaasahan. Gusto naming ang mas mababang mga bagay-bagay na sa sa simula, at ang mas mataas na mga bagay-bagay na sa dulo. 

Paano namin gawin ito? Well sa pseudocode code, maaari naming sabihin, sabihin magtakda ng isang swap counter sa isang non-zero na halaga. Susubukan naming makita kung bakit ginagawa namin na sa isang segundo. At pagkatapos ay ulitin namin ang mga sumusunod na proseso hanggang sa swap counter ay 0, o hanggang hindi kami gumagawa nang swaps sa lahat. 

I-reset ang magpalitan ng kontra sa 0 kung wala pa ito 0. Pagkatapos ay tumingin sa bawat katabi pares ng mga elemento. Kung ang mga dalawang mga elemento ay wala sa pagkakasunod-sunod, magpalitan ng mga ito, at magdagdag ng 1 sa swap counter. Kung pinag-iisipan mo tungkol sa ito bago mo maisalarawan ito, mapapansin na ito ay malilipat sa mas mababang minamahal na mga elemento sa kaliwa at mas mataas na pinahahalagahan elemento sa kanan, epektibong paggawa ng kung ano ang gusto naming gawin, na kung saan ay ilipat ang mga grupo ng mga elemento sa paraang iyon. Ni mailarawan kung paano ito Hayaan maaaring tumingin sa paggamit ng aming array na ginamit namin upang subukan ang out ang mga algorithm. Kami ay may isang unsorted array dito muli, ipinapahiwatig ng lahat ng mga elemento pagiging sa pula. At inilagay ko ang aking swap counter sa isang nonzero halaga. Nagkataon pinili ko negatibong 1-- ito ay hindi 0. Gusto naming ulitin ang prosesong ito hanggang sa swap counter ay 0. Ito ang dahilan kung bakit ko itatakda ang aking swap kontra sa ilang mga di-zero na halaga, dahil kung hindi, ang swap counter ay 0. Hindi namin ay magsisimula sa proseso ng algorithm. Kaya muli, ang mga hakbang are-- i-reset ang swap counter sa 0, pagkatapos ay tumingin sa bawat kalapit pares, at kung ang mga ito sa labas ng order, magpalitan ng mga ito, at magdagdag ng 1 sa swap counter. Kaya simulan ni prosesong ito hayaan. Kaya ang unang bagay na namin ay namin-set ang magpalitan counter sa 0, at pagkatapos ay simulan namin ang pagtingin sa bawat katabing pares. 

Kaya una naming simulan ang pagtingin sa 5 at 2. Nakita namin na ang mga ito ay sa labas ng order at iba swap namin sa kanila. At idagdag namin ang 1 sa swap counter. Kaya ngayon ang aming swap counter ay 1, at 2 at 5 ay nakabukas. Ngayon kami ulitin ang proseso muli. 

Inaasahan naming sa mga susunod na katabi pair, 5 at 1-- ang mga ito ay din sa labas ng order, kaya swap namin ang mga ito at idagdag ang 1 sa swap counter. Pagkatapos namin tumingin sa 5 at 3. Ang mga ito ay sa labas ng order, kaya magpalit kami ang mga ito at kami ay magdagdag ng 1 sa swap counter. Pagkatapos namin tumingin sa 5 at 6. Ang mga ito sa pagkakasunud-sunod, para hindi namin talagang kailangang magpalit ng anumang bagay oras na ito. Pagkatapos namin tumingin sa 6 at 4. Ang mga ito ay din sa labas ng order, kaya magpalit kami ang mga ito at kami ay magdagdag ng 1 sa swap counter. 

Ngayon pansinin kung ano ang nangyari. Inilipat kami ng 6 na ang lahat ng mga paraan sa dulo. Kaya sa pagpili ng uri, kung na sa iyo nakita video na iyon, kung ano ang aming ginawa ay napunta kami ng paggalaw sa pinakamaliit na sangkap sa gusali ang pinagsunod-sunod array mahalagang mula kaliwa hanggang kanan, pinakamaliit sa pinakamalaking. Sa kaso ng bubble uri, kung hindi namin sumusunod sa partikular na algorithm, aktwal na kami ay pagpunta sa pagbuo ng ang pinagsunod-sunod array mula sa kanan sa kaliwa, pinakamalaking sa pinakamaliit. Mabisa namin bubbled 6, ang pinakamalaking halaga, ang lahat ng mga paraan sa dulo. 

At upang maaari naming ngayon idedeklara na iyon ay inayos, at sa hinaharap iterations-- pagpunta sa pamamagitan ng array again-- hindi namin ay may upang isaalang-alang 6 anymore. Kami lamang magkaroon ng upang isaalang-alang unsorted elemento kapag kami ay naghahanap sa katabing pares. Tapos Kaya kami isa pumasa sa pamamagitan ng bubble sort. Kaya ngayon kami bumalik sa mga tanong, ulitin hanggang sa swap counter ay 0. Well ang magpalitan counter ay 4, kaya kami ay pagpunta upang panatilihin ang paulit-ulit na muli ang proseso na ito. 

Kami ay pagpunta upang i-reset ang magpalitan counter sa 0, at tingnan ang bawat katabing pares. Kaya namin magsimula sa 2 at 1-- na ang mga ito sa labas ng order, kaya swap namin ang mga ito at idagdag namin 1 sa swap counter. 2 at 3, ang mga ito sa pagkakasunud-sunod. Hindi natin kailangan na gawin ang anumang bagay. 3 at 5 ay nasa ayos. Hindi natin kailangan gumawa ng kahit ano doon. 

5 at 4, sila ay out ng order, at gayon din kami kailangan upang magpalitan ng mga ito at idagdag ang 1 sa swap counter. At ngayon kami ay inilipat 5, ang susunod na pinakamalaking sangkap, sa dulo ng unsorted bahagi. Kaya maaari na ngayong tumawag namin na bahagi ng pinagsunod-sunod na bahagi. 

Ngayon ikaw ay naghahanap sa screen at marahil ay maaaring sabihin, hangga't makakaya ko, na ang mga array ay inayos ngayon. Ngunit hindi pa namin maaaring patunayan na. Hindi namin magkaroon ng isang garantiya na ito ay pinagsunod-sunod. Ngunit ito ay kung saan ang swap counter ang pagpunta sa dumating sa play. 

Kaya naming makumpleto ang isang pass. Ang swap counter ay 2. Kaya kami ay pagpunta sa ulitin muli ang proseso na ito, ulitin hanggang sa swap counter ay 0. I-reset ang magpalitan counter sa 0. Kaya makikita reset namin ito. 

Ngayon ay tumingin sa bawat katabing pares. Iyan ay sa order, 1 at 2. 2 at 3 ay sa order. 3 at 4 ay nasa ayos. Kaya sa puntong ito, ang paunawa naming makumpleto ang pagtingin sa bawat kalapit na pares, ngunit ang swap counter ay 0 pa rin. 

Kung hindi namin ay may upang lumipat sa anumang mga sangkap, at pagkatapos na sila dapat na sa order, sa pamamagitan ng kabutihan ng prosesong ito. At kaya isang kahusayan ng mga uri, pag-ibig na ang mga siyentipiko namin computer, ay maaari na namin ngayon idedeklara ang buong array ay dapat pinagsunod-sunod, dahil kami ay hindi kung magpalit ng anumang elemento. Iyan ay medyo nice. 

Kaya kung ano ang pinakamasama kaso sitwasyon na may bubble sort? Sa pinakamasama kaso array ay sa ganap reverse order, at kaya kami ay may sa bubble bawat ng malaking elemento ang lahat mga paraan sa buong array. At kami rin epektibo kung bubble ang lahat ng maliit na mga elemento sa likod ang lahat ng mga paraan sa buong array, masyadong. Kaya bawat isa sa mga n elemento ay may upang ilipat sa lahat ng iba pang mga n elemento. Kaya na ang pinakamasama sitwasyon kaso. Sa pinakamahusay na kaso senaryo bagaman, ito ay bahagyang naiiba mula sa mga uri ng pagpili. Ang array ay nai Inayos kapag pumunta kami in. Hindi namin kailangang gumawa ng anumang swaps sa unang pass. Kaya maaari naming magkaroon upang tumingin sa mas kaunting mga elemento, tama? Hindi natin kailangang ulitin ito proseso ang isang bilang ng mga beses sa loob. 

Kaya kung ano ang ibig sabihin nito? Kaya kung ano ang pinakamasama kaso sitwasyon para sa bubble-uuri, at kung ano ang ang pinakamahusay na kaso sitwasyon para sa bubble sort? Hulaan mo ba ito? Sa pinakamasama kaso kailangan mong umulit sa lahat ng mga elemento n n ulit. Kaya ang pinakamasama kaso ay n nakalapat. 

Kung ang array ay ganap na ganap Pinagbukud-bukod bagaman, ikaw lamang kung tumingin sa bawat ng mga elemento ng isang beses. At kung ang swap counter ay 0 pa rin, maaari mong sabihin na ito array ay inayos. At kaya sa pinakamahusay na kaso, ito ay talagang mas mahusay kaysa sa pagpili sort-- ito ay katapusan ng n. 

Ako Doug Lloyd. Ito ay CS50.