Bubble slags er en af ​​de nemmeste slags algoritmer. Det kaldes boble sortere , fordi den vil " boble " værdier i din liste til toppen ( eller bunden afhængigt af hvordan du tænker på det). Selv om det er en nem sortering , er det ikke nær så effektiv som mere avancerede slags, og bør kun virkelig bruges i uddannelsesøjemed ( medmindre du kender din liste er næsten sorteret, i hvilket tilfælde det er ikke dårligt ) Ting du skal < br > En computer, der kan samle nogle programmeringssprog OR
Blyant og papir til at gå gennem eksempel
Vis Flere Instruktioner
1

jeg tror, ​​den bedste måde at diskutere boble sortere er med et eksempel . Jeg vil give et overblik over den algoritme , og så vil vi arbejde gennem et eksempel trin -for-trin for at give dig en idé om, hvordan det fungerer. Så det første, ideen.
2

Bubble sortere bruges til at sortere en liste over emner i stigende eller faldende rækkefølge . Lad os antage, for denne slags , som du ønsker at sætte listen i stigende rækkefølge (dvs. 1,2,3 , etc.). Den slags virker ved at passere over hvert element på din liste og sammenligne det med det næste element i listen . Hvis det første element er større end det andet element er de to skiftes . Hvis det første element er mindre end eller lig med det andet , sker der ingenting . Efter at have kigget på dette element , er det næste element kigget på, og processen gentages .
3

Når den slags har kigget på hvert element , har man ' pass' afsluttet. Efter en pass, ved du med sikkerhed, at et nummer skal være i den rigtige position . I vores stigende rækkefølge , vil den største værdi "boble" til slutningen af ​​listen. Desværre , du ikke kender , hvis resten af ​​listen er sorteret , så du er nødt til at tage en anden pass . Men på denne pass , kan du stoppe et element før udgangen , da du ved, at antallet allerede er i den korrekte position.
4

Bubble slags ( som regel) kræver flere omgange at fuldføre. De fleste passerer det vil kræve , er lig med antallet af elementer på listen minus 1 . Så hvis du har 10 elementer i din liste, kan det tage 9 gennemløb for at fuldføre den slags. Lad os gå igennem et eksempel for bedre at forklare det
5

Lad os bruge følgende usorteret liste: . 6, 3 , 1, 8 , 2, 4 fotos

Vi vil gerne listen se sådan ud: 1, 2, 3, 4 , 6, 8

på den første pass , vil vi sammenligne tallene én ad gangen , og vi ved, at efter en pass vi skal have det største antal hele vejen til højre , så i dette tilfælde vil det være 8. . For vores eksempel vil ^ tegnet pege på stedet i listen, som vi i øjeblikket er ved at undersøge.
6

6, 3 , 1, 8 , 2, 4 fotos

Pass 1 , trin 1 ) Sammenlign de 6 og 3. . 6 er større end 3 , så vi bytte them.3 , ^ 6 , 1, 8 , 2, 4 fotos

Pass 1 , trin 2) Sammenlign 6 og 1. . 6 er større end 1 , så vi bytte them.3 , 1, ^ 6, 8 , 2, 4 fotos

Pass 1 , trin 3) Sammenlign 6 og 8 . 6 er mindre end eller lig med 8 , så intet happens.3 , 1, 6, ^ 8 , 2, 4 fotos

Pass 1, trin 4 ) Sammenlign de 8 og 2. . 8 er større end 2, så bytte them.3 , 1, 6, 2, ^ 8 , 4 fotos

Pass 1, Trin 5) Sammenlign 8 og 4. . 8 er større end 4, så bytte them.3 , 1, 6, 2, 4, 8

Og du er færdig den første pass !
7

3, 1, 6, 2 , 4, 8 er næppe en sorteret liste , men du kan se , som lovet , de 8 er på enden . Jeg vil nu skrive ud af, hvad listen ser ud efter hvert gennemløb . Prøv det selv , og se, om din matcher mine: Pass 2: 1, 3, 2, 4 , 6, 8 (ser bedre) Pass 3: 1 , 2, 3 , 4, 6 , 8 ( gjort) Pass 4: 1 , 2, 3 , 4, 6 , 8 ( umm ... var vi ikke allerede har gjort? ) Pass 5: ( ! stadig gjort) 1, 2, 3, 4 , 6, 8
8 < p> Som du kan se , blev listen sorteres efter 3 omgange , men boblen slags holdes i gang. Hvorfor er det? Nå, den grundlæggende boble sortere algoritme er temmelig dum . Den ønsker at sikre, at det vil fungere i værste fald (som er en liste, der er helt bagud ligesom 9, 8, 7, 6, 5). Du kan tilføje en hastighed op til at gøre din boble sortere køre lidt hurtigere. På hver pass, har et flag , der bliver sat til true KUN hvis du rent faktisk skifter to numre. Før du gør det næste pass, at se om flaget er sande eller falske. Hvis det er sandt , du byttede to numre , og du er nødt til at gøre en anden pass . Hvis det er falsk , er din liste sorteret , og du kan gøres. I vores eksempel , selvom listen blev sorteret efter 3 omgange ville vi stadig nødt til at gøre en 4th pass , fordi vi lavede en swap i 3. pass .
9

Nu ved du , hvordan du gør en boble slags. Efterlade kommentarer med eventuelle spørgsmål, du måtte have. Tak for læsning !