[Powered by Google Translate] [Rendit flluskoj] [JACKSON STEINKAMP Universitetin e Harvardit] [KJO ËSHTË CS50. CS50TV] Rendit Bubble është një shembull i një algoritmi klasifikim - që është, një procedurë për klasifikim e një sërë elementeve në ngjitje apo rend zbritës. Për shembull, në qoftë se ju të kërkuar për të zgjidhur një rrjet i përbërë nga numrat [3, 5, 2, 9], një zbatimi korrekt i Renditur Bubble do të kthejë grup renditura [2, 3, 5, 9] në ngjitje rendin. Tani, unë jam duke shkuar për të shpjeguar në pseudokod si algorithm punon. Le të thonë se ne jemi zgjidhja një listë prej 5 integers - 3, 2, 9, 6, dhe 5. Algorithm fillon duke shikuar në dy elementet e para, 3 dhe 2, dhe kontrolluar nëse ata janë jashtë rendit të afërm me njëri-tjetrin. Ata janë - 3 është më i madh se 2. Të jetë në mënyrë ngjitje, ata duhet të jenë mënyra të tjera përreth. Pra, ne bie në ujdi tyre. Tani lista duket si ky: [2, 3, 9, 6, 5]. Tjetra, ne shikojmë në elementet e dytë dhe të tretë, 3 dhe 9. Ata janë në mënyrë të saktë në lidhje me njëri-tjetrin. Kjo është, është më pak se 3 9 kështu që algoritmi nuk bie në ujdi tyre. Tjetra, ne shikojmë në 9 dhe 6. Ata janë jashtë funksionit. Pra, ne duhet të bie në ujdi ato, sepse është më i madh se 9 6. Së fundi, ne shikojmë në të dy integers fundit, 9 dhe 5. Ata janë jashtë funksionit, kështu që ata duhet të shkëmbehen. Pas kalimit të parë nëpër lista e plotë, ajo duket si kjo: [2, 3, 6, 5, 9]. Jo keq. Është pothuajse e renditura. Por ne kemi nevojë për të drejtuar nëpër lista për të marrë atë përsëri zgjidhet plotësisht. Dy është më pak se 3, kështu që ne nuk do të bie në ujdi tyre. Tre është më pak se 6, kështu që ne nuk do të bie në ujdi tyre. Gjashtë është më i madh se 5. Ne swapped. Gjashtë është më pak se 9. Ne nuk bie në ujdi. Pas kalojë përmes dytë, ajo duket si ky: [2, 3, 5, 6, 9]. Përsosur. Tani, le të shkruajë atë në pseudokod. Në thelb, për çdo element në listë, ne duhet të shohim në atë dhe elementi i drejtpërdrejtë në të djathtë të tij. Nëse ata janë jashtë rendit të afërm me njëri-tjetrin - që është, në qoftë se elementi në të majtë është më i madh se ai në të djathtë - ne duhet të bie në ujdi dy elemente. Ne e bëjmë këtë për çdo element të listës, dhe ne kemi bërë një të kalojë përmes. Tani ne vetëm duhet të bëni të kalojë përmes-herë të mjaftueshme për të siguruar listën është plotësisht, të renditura siç duhet. Por sa herë nuk kemi të duhet të kalojnë nëpër lista për të garantoj se ne jemi duke bërë? E pra, rastin më të keq është nëse ne kemi një listë plotësisht prapa. Pastaj ajo merr një numër të kalojnë-throughs barabartë me numrin i elementeve n-1. Nëse kjo nuk ka kuptim intuitive, të mendojnë për një rast të thjeshtë - lista [2, 1]. Kjo do të marrë një të kalojë nëpër-për të zgjidhur saktë. [3, 2, 1] - Rasti më i keq është se me 3 elemente të renditura prapa, ajo do të marrë 2 iterations për të zgjidhur. Pas një përsëritje, ajo është [2, 1, 3]. Rendimentet dyta array renditura [1, 2, 3]. Pra, ju e dini që ju nuk duhet të kalojnë nëpër rrjet, në përgjithësi, më shumë se n-1 herë, ku n është numri i elementeve në vektorit. Ajo që quhet Rendit Bubble sepse elementet më të mëdha kanë tendencë për të "flluskë-up ' në të djathtë shumë shpejt. Në fakt, ky algoritëm ka sjellje shumë interesante. Pas iterations m përmes grup të tërë, elementet rightmost m janë të garantuara të zgjidhet në vendin e tyre të saktë. Nëse ju doni të shihni këtë për veten tuaj, ne mund ta provoni atë në një listë të plotë prapa [9, 6, 5, 3, 2]. Pas një të kalojë nëpër gjithë listën, [Të shëndoshë e të shkruarit] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] elementi rightmost 9 është në vendin e vet të duhur. Pasi e dytë të kalojë nëpër-, 6 do të ketë 'bubbled-up' të Vendin e dytë rightmost. Dy elementet në të djathtë - 6 dhe 9 - do të jenë në vendet e tyre të saktë pas para dy Pass-throughs. Pra, si mund të përdorni këtë për të optimizuar algorithm? E pra, pas një përsëritje nëpërmjet rrjet ne nuk të vërtetë nevojë për të kontrolluar elementin rightmost sepse ne e dimë se është renditura. Pas dy iterations, ne e dimë për të siguruar rightmost dy elemente janë në vend. Pra, në përgjithësi, pasi iterations k përmes koleksion të plotë, kontrolluar elementet e fundit k është i tepërt pasi ne e dimë ata janë në vendin e saktë tashmë. Pra, nëse ju jeni zgjidhja një sërë elementesh n, në përsëritje parë - you'll keni për të zgjidhur të gjitha elementet - e parë n-0. Në përsëritje të dytë, ju do të duhet të shikojmë në të gjitha elementet, por e fundit - parë n-1. Një tjetër optimization mund të jetë për të kontrolluar nëse lista është renditur tashmë pas çdo përsëritje. Nëse është e renditur tashmë, ne nuk kemi nevojë për të bërë ndonjë iterations më shumë nëpër lista. Si mund ta bëjë këtë? E pra, në qoftë se ne nuk do të bëjë ndonjë këmbime në një të kalojë nëpër-i listës, është e qartë se lista u renditur tashmë, sepse nuk kemi asgjë të bie në ujdi. Pra, ne definitivisht nuk kanë për të zgjidhur përsëri. Ndoshta ju mund të nisja një ndryshore të quajtur flamur 'nuk zgjidhet' për të rreme dhe për të ndryshuar atë për të vërtetë në qoftë se ju keni të bie në ujdi ndonjë elementet në një përsëritje nëpër rrjet. Apo të ngjashme, të bëjë një kundër për të numëruar sa këmbime të bëni në çdo përsëritje të dhënë. Në fund të një përsëritje, në qoftë se ju nuk e keni të bie në ujdi ndonjë prej elementeve, ju e dini listë është renditur tashmë dhe ju jeni bërë. Rendit Bubble, si algoritme zgjidhja e tjera, mund të jetë tweaked për të punuar për ndonjë elemente të cilat kanë një metodë urdhërimin. Kjo është, duke pasur parasysh dy elementë që ju keni një mënyrë për të thënë nëse pari është më e madhe se, ose të barabartë me më pak se dytë. Për shembull, ju mund të lloj shkronja të alfabetit duke thënë se a