[Powered by Google Translate] [Bubble-uri-uriin ang] [Jackson STEINKAMP Harvard University] [ITO AY CS50. CS50TV] -Uri-uriin ng bubble ay isang halimbawa ng algorithm ng pag-uuri-uri - na, ang isang pamamaraan para sa pag-uuri-uri sa isang hanay ng mga elemento sa pataas o pababang ayos. Halimbawa, kung gusto mo upang pag-uri-uriin ang isang array binubuo ng ang mga numero [3, 5, 2, 9], tamang pagpapatupad ng Bubble-uri-uriin ang ibalik ang pinagsunod-sunod array [2, 3, 5, 9] sa pataas na pagkakasunod-sunod. Ngayon, ako pagpunta sa ipaliwanag sa pseudocode kung paano gumagana ang algorithm sa. Ipagpalagay natin na namin ang pag-uuri-uri ng isang listahan ng 5 integer - 3, 2, 9, 6, at 5. Algorithm ay nagsisimula sa pamamagitan ng pagtingin sa ang unang dalawang mga elemento, 3 at 2, at check kung sila ng order na may kaugnayan sa bawat isa. Ang mga ito ay - 3 ay mas malaki kaysa sa 2. Upang maging sa pataas na pagkakasunod-sunod, dapat silang maging ang iba pang mga paraan sa paligid. Kaya, swap namin sa kanila. Ngayon tinitingnan ang listahan tulad nito: [2, 3, 9, 6, 5]. Susunod, tinitingnan namin ang pangalawa at pangatlong elemento, 3 at 9. Na ang mga ito sa tamang pagkakasunod-sunod na may kaugnayan sa bawat isa. Iyon ay, 3 ay mas mababa sa 9 kaya algorithm ay hindi swap sa kanila. Susunod, tinitingnan namin ang 9 at 6. Ang mga ito ng pagkakasunod-sunod. Kaya, kailangan naming i-swap sa kanila dahil 9 ay mas malaki kaysa sa 6. Panghuli, hanapin namin sa huling dalawang integer, 9 at 5. Ang mga ito ng pagkakasunod-sunod, kaya dapat sila ay swapped. Pagkatapos ng unang kumpletong pass sa pamamagitan ng listahan, Mukhang ito: [2, 3, 6, 5, 9]. Hindi masama. Halos Ito ay pinagsunod-sunod. Ngunit kailangan namin upang tumakbo muli sa pamamagitan ng listahan upang makakuha ng ganap na pinagsunod-sunod. Dalawang ay mas mababa sa 3, kaya hindi namin swap sa kanila. Tatlong ay mas mababa sa 6, kaya hindi namin swap sa kanila. Anim ay mas malaki kaysa 5. Namin swapped. Anim ay mas mababa sa 9. Hindi namin magpalitan. Pagkatapos ng pangalawang pass sa pamamagitan, ay ganito ang hitsura: [2, 3, 5, 6, 9]. Perpekto. Ngayon, sabihin sumulat ito sa pseudocode. Talaga, para sa bawat elemento sa listahan, kailangan namin upang tingnan ito at ang mga elemento nang direkta sa kanan. Kung ang mga ito ay sira na may kaugnayan sa bawat isa - iyon ay, kung ang elemento sa kaliwa ay mas mataas kaysa sa isa sa kanan - dapat naming magpalitan ng dalawang elemento. Ginagawa namin ito para sa bawat elemento ng listahan, at gumawa kami ng isang pass sa pamamagitan ng. Ngayon lang namin upang gawin ang pass-through na sapat na oras upang matiyak ang listahan ay ganap na, maayos na pinagsunod-sunod. Ngunit kung gaano karaming beses ang mayroon kaming upang pumasa sa pamamagitan ng listahan magagarantiya na tapos na kami? Well, ang pinakamasama-case na sitwasyon ay kung kami ay may isang ganap na paurong listahan. Pagkatapos ito ay tumatagal ng isang bilang ng mga pumasa-through na katumbas ng bilang ng mga elemento n-1. Kung ito ay hindi magkaroon ng kahulugan intuitively, sa tingin ng isang simpleng kaso - ang listahan [2, 1]. Ito ay pagpunta sa tumagal ng isang pass-through na upang pag-uri-uriin ang tama. [3, 2, 1] - Ang pinakamasama kaso na may 3 mga elemento pinagsunod-sunod paurong, ito ay tumagal ng 2 iterations pagbukud-. Pagkatapos ng isang pag-ulit, [2, 1, 3]. Ang pangalawang magbubunga ang pinagsunod-sunod na array [1, 2, 3]. Kaya alam mong hindi mo kailangang pumunta sa pamamagitan ng array, sa pangkalahatan, higit pa kaysa sa n-1 beses, kung saan ang n ay ang bilang ng mga elemento sa array. Ito ay tinatawag na-uri-uriin ng Bubble dahil ang pinakamalaking elemento ay may posibilidad na 'bubble-up' sa kanan medyo mabilis. Sa katunayan, ang algorithm na ito ay lubhang kawili-wili pag-uugali. Pagkatapos m iterations sa pamamagitan ng buong array, ang rightmost m elemento ay katiyakan na pinagsunod-sunod sa kanilang tamang lugar. Kung nais mong makita ito para sa iyong sarili, maaari naming subukan ito sa ganap na paurong listahan [9, 6, 5, 3, 2]. Pagkatapos ng isang pass sa pamamagitan ng buong listahan, [Tunog ng pagsulat] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] rightmost elemento 9 ay nasa tamang lugar nito. Pagkatapos ng pangalawang pass-through, ang 6 ay may 'bubbled-up' sa pangalawang rightmost lugar. Ang dalawang mga elemento sa kanan - 6 at 9 - sa kanilang mga tamang lugar pagkatapos ng unang dalawang pass-through. Kaya, kung paano namin gamitin ito upang i-optimize ang algorithm? Well, pagkatapos ng isang pag-ulit sa pamamagitan ng array hindi namin aktwal na kailangan upang suriin ang rightmost elemento dahil alam namin ito pinagsunod-sunod. Pagkatapos ng dalawang iterations, alam namin para bang rightmost dalawang mga elemento sa lugar. Kaya, sa pangkalahatan, pagkatapos k iterations sa pamamagitan ng buong array, check ang huling elemento sa k ay kalabisan dahil alam namin ang mga ito sa tamang lokasyon. Kaya kung ikaw ay pag-uuri-uri ng isang array ng mga elemento n, sa unang pag-ulit - you'll upang pag-uri-uriin ang lahat ng mga elemento - ang unang n-0. Sa pangalawang ulit, magkakaroon ka upang tumingin sa lahat ng mga elemento ngunit ang huling - ang unang n-1. -Optimize ng isa pang maaaring upang suriin kung ang listahan na pinagsunod-sunod pagkatapos ng bawat pag-ulit. Kung ito pinagsunod-sunod, hindi namin kailangang gumawa ng anumang higit pang mga iterations sa pamamagitan ng listahan. Paano namin gawin ito? Well, kung hindi kami gumawa ng anumang mga swaps sa isang pass-through ng listahan, malinaw na listahan ay pinagsunod-sunod dahil hindi namin magpalitan ng anumang. Kaya tiyak namin ay hindi upang pag-uri-uriin muli. Siguro maaari mong simulan ang isang flag variable na tinatawag na 'hindi pinagsunod-sunod' sa mali at baguhin ito sa true kung mayroon kang magpalitan anumang mga elemento sa isa-ulit sa pamamagitan ng array. O katulad, gumawa ng isang counter sa bilang ng kung gaano karaming mga swaps gumawa ka sa anumang naibigay na ulit. Sa dulo ng isang pag-ulit, kung hindi mo swap ang alinman sa mga elemento, alam mo listahan na pinagsunod-sunod at tapos ka na. Bubble-uri-uriin, tulad ng iba pang mga pag-uuri algorithm, maaari tweaked upang gumana para sa anumang mga elemento na kung saan ay mayroon ng isang pag-order paraan ng. Iyon ay, naibigay dalawang elemento mayroon kang isang paraan upang sabihin kung ang unang ay mas malaki kaysa sa, na katumbas ng o mas mababa kaysa sa ikalawang. Halimbawa, maaari mong pag-uri-uriin ang mga titik ng alpabeto sa pamamagitan ng sinasabi na isang