Ako to urobiť Bubble druh

Bubble sort je jeden z najjednoduchších algoritmov radenia . To sa nazýva bubble sort , pretože to bude " bublina " hodnoty v zozname na hornej ( alebo dolnej časti v závislosti na tom , ako si myslíte , že na to ) . Aj keď je ľahké triedenie , to nie je zďaleka tak efektívne ako pokročilejšie druhy , a mala by byť naozaj použité výhradne k návodom účely ( ak viete , že váš zoznam je takmer radené , v tom prípade , že to nie je zlé ) Veci , ktoré budete potrebovať
Počítač , ktorý je možné zostaviť nejaký programovací jazyk alebo
Ceruzka a papier prejsť napríklad
Zobraziť ďalšie inštrukcie Cestuj 1

Myslím , že najlepší spôsob, ako diskutovať bubliny druhu je s príkladom . Dám prehľad algoritmu , a potom budeme pracovať pomocou príkladu krok - za - krokom , aby vám predstavu o tom , ako to funguje . Tak za prvé, myšlienka .
2

Bubble sort sa používa pre triedenie zoznamu položiek do vzostupné alebo klesajúce poradie . Predpokladajme , že pre tento druh , ktorý chcete vložiť do zoznamu vo vzostupnom poradí ( tj 1,2,3 , atď ) . Triediť funguje tým , že prejde cez každý prvok v zozname a porovnajte ju s ďalší prvok v zozname . Keď je prvý prvok je väčší ako druhý prvok , dva sú zapnuté . Keď je prvý prvok je menší ako alebo rovný druhému , nič sa nedeje . Potom, čo pri pohľade na tento prvok , ďalší prvok sa pozrel na , a proces sa opakuje .
3

radenia sa pozrel na každý prvok , jeden " priechod " bol dokončený . Po jednom priechodu , viete isto , že jedno číslo musí byť v správnej polohe . V našom vzostupnom poradí , bude " bublina " na koniec zoznamu najväčšia hodnota . Bohužiaľ , neviem, či zvyšok zozname sú uvedené , takže budete musieť vziať ďalšiu prihrávka . Avšak, na tomto priechode , môžete zastaviť jeden prvok pred koncom, pretože viete , že číslo je už v správnej polohe .
4

Bubble sort ( zvyčajne ) vyžaduje niekoľko povolenie na dokončenie . Najviac prejde to bude vyžadovať , sa rovná počtu prvkov v zozname mínus 1. Takže ak máte 10 prvkov v zozname , môže to trvať 9 prechádza k dokončenie druhu . Poďme si prejsť napríklad lepšie vysvetliť
5

Poďme použite nasledujúci netriedeného zoznamu : . 6 , 3 , 1 , 8 , 2 , 4

Dovoľujeme si zoznam , aby vyzerať takto : 1 , 2 , 3 , 4 , 6 , 8

Na prvom prechode , budeme porovnávať jeden čísiel naraz , a vieme , že po jednom prechode by sme mali mať najväčší počet úplne doprava , takže v tomto prípade , že bude 8. Pre náš príklad , bude ^ znamenia poukazujú na mieste v zozname , ktorý sa v súčasnosti skúma .
6

6 , 3 , 1 , 8 , 2 , 4

priechod 1 , Krok 1 ) Porovnajte 6 a 3. 6 je väčší ako 3 , takže budeme vymieňať them.3 , ^ 6 , 1 , 8 , 2 , 4

priechod 1 , krok 2 ) Porovnajte 6 a 1. 6 je väčší ako 1 , takže budeme vymieňať them.3 , 1 , ^ 6 , 8 , 2 , 4

priechod 1 , krok 3 ) Porovnajte 6 a 8. 6 je menšie ako alebo rovná 8 , takže nič happens.3 , 1 , 6 , 8 ^ , 2 , 4 celým

priechod 1 , krok 4 ) Porovnajte 8 a 2. 8 je väčší ako 2 , a tak swap them.3 , 1 , 6 , 2 , ^ 8 , 4 celým

priechod 1 , Krok 5 ) Porovnajte 8 a 4. 8 je vyšší ako 4 , takže výmena them.3 , 1 , 6 , 2 , 4 , 8

A máte hotovo prvý priechod !
7

3 , 1 , 6 , 2 , 4 , 8 je ťažko radené zoznam , ale môžete vidieť , ako som sľúbil , 8 je na konci . Budem teraz napísať , čo zoznam vyzerá ako po každom priechode . Skúste si to sami , a uvidíme , či vás moja zápasov : Heslo 2 : 1 , 3 , 2 , 4 , 6 , 8 ( vyzerá lepšie ) Heslo 3 : 1 , 2 , 3 , 4 , 6 , 8 ( vykonaný) Heslo 4 : 1 , 2 , 3 , 4 , 6 , 8 ( ? umm ... neboli sme už urobili ) Heslo 5 : 1 , 2 , 3 , 4 , 6 , 8 ( ! stále vykonáva )
8

Ako vidíte , zoznam bol ďalej po 3 priechodoch , ale bublina trochu ďalej . Prečo je to tak ? No , základné bublina radiaca algoritmus je celkom hlúpe . Chce , aby sa ubezpečil , že to bude fungovať v najhoršom prípade ( čo je zoznam , ktorý je úplne dozadu ako 9 , 8 , 7 , 6 , 5 ) . Môžete pridať rýchlosť tak , aby bola vaša bublina trochu bežať trochu rýchlejšie . Na každom priechode , majú príznak , ktorý sa nastavená na hodnotu true iba ak ste skutočne prepínať dve čísla . Než začnete robiť ďalšie prihrávku , skontrolujte , či je príznak true alebo false . Ak je to pravda , si vymenil dve čísla , a čo musíte urobiť , ďalšie prihrávka . Ak je false , zoznam je triedený , a vy môžete byť vykonané . V našom prípade , a to aj napriek tomu , že zoznam bol ďalej po 3 priechodoch , budeme ešte potrebovať , aby sa štvrtý prihrávku , pretože sme urobili výmenu v 3. priesmyku .
9

Teraz viete , ako to urobiť bubble sort . Zanechať komentár s prípadnými otázkami môžete mať . Vďaka za prečítanie !

• Predchádzajúca strana: Základy programovania Pomocník 
• Ďalšia strana: Ako sa učiť Prológ