Bubble sort er en av de enkleste sortere algoritmer. Det kalles boble slags fordi det skal " boble " verdier i listen til toppen ( eller bunnen avhengig av hvordan du tenker på det). Mens det er en enkel form , er det ikke på langt nær så effektiv som mer avanserte former, og bør egentlig bare brukes til læring (med mindre du vet at listen er nesten sortert, og da er det ikke ille ) er hva du trenger
En datamaskin som kan kompilere noen programmeringsspråk eller
Blyant og papir for å gå gjennom eksempelet
Vis flere instruksjoner
en

tror jeg den beste måten å diskutere boble sortere er med et eksempel . Jeg skal gi en oversikt over algoritmen , og så får vi jobbe gjennom et eksempel steg-for- steg for å gi deg en idé om hvordan det fungerer. Så først , ideen .
2

Bubble sortere brukes til å sortere en liste over elementer i stigende eller synkende rekkefølge . La oss anta for denne typen som du ønsker å sette på listen i stigende rekkefølge ( 1,2,3 dvs. etc. ) . Den slags virker ved å passere over hvert element i listen, og sammenligne den med neste element i listen . Dersom det første elementet er større enn det andre elementet, føres de to byttet . Hvis det første element er mindre enn eller lik den andre , skjer det ingen ting. Etter å se på dette elementet , er det neste elementet så på, og prosessen gjentar .
3

Når sorteringen har sett på hvert element , har en 'pass ' er ferdig . Etter ett pass , vet du sikkert at ett tall må være i riktig posisjon . I vår stigende rekkefølge , den største verdien vil " boble " på slutten av listen . Dessverre , du vet ikke om resten av listen er sortert , så du må ta en annen pass . Men på denne pass, kan du stoppe ett element før slutten siden du vet at nummeret allerede er i riktig posisjon .
4

Bubble sort ( vanligvis) krever flere omganger for å fullføre . De fleste passerer det vil kreve er lik antallet av elementer i listen minus 1 . Så hvis du har 10 elementer i listen, kan det ta ni går for å fullføre sorteringen. La oss gå gjennom et eksempel for å bedre forklare det
5

La oss bruke følgende usortert liste : . 6, 3, 1 , 8, 2 , 4

Vi ønsker listen til se slik ut: 1 , 2, 3 , 4, 6 , 8

på første pass , vil vi sammenligne tallene en om gangen , og vi vet at etter en pasning bør vi ha størst antall helt til høyre, slik at i dette tilfellet vil det være åtte . For vårt eksempel , vil ^ skilt peker til stedet i listen som vi nå undersøker .
6

6 , 3, 1 , 8, 2 , 4

Pass 1 , Trinn 1 ) Sammenlign 6 og 3. . 6 er større enn tre , så vi får bytte them.3 , ^ 6 , 1 , 8, 2 , 4

Pass 1 , Trinn 2 ) Sammenlign seks og en . 6 er større enn 1 , så vi får bytte them.3 , 1 , ^ 6 , 8, 2 , 4

Pass 1 , trinn 3) Sammenlign seks og åtte . 6 er mindre enn eller lik 8, så ingenting happens.3 , 1 , 6, ^ 8 , 2 , 4

en Pass, 4 Step ) Sammenlign åtte og to . 8 er større enn 2 , så bytte them.3 , 1 , 6, 2, ^ 8 , 4

Pass 1 , 5 trinn ) Sammenlign åtte og fire . 8 er større enn fire , så bytte them.3 , 1 , 6, 2 , 4, 8

Og du er ferdig første pass !
7

3, 1 , 6 , 2, 4 , 8 er neppe en sortert liste , men du kan se, som lovet , er åtte på slutten. Jeg skal nå skrive ut hva listen ser ut etter hver passering . Prøv selv , og se om din passer meg : 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 gjort? ) Pass 5 : ( ! fortsatt gjøres ) 1 , 2, 3 , 4, 6, 8
8 < p> Som du kan se, ble listen sortert etter 3 pasninger , men boblen slags holdt det gående. Hvorfor det? Vel , er den grunnleggende boble slags algoritme ganske dum . Den ønsker å være sikker på at det vil fungere i verste fall ( som er en liste som er helt bakover som 9 , 8, 7 , 6, 5 ) . Du kan legge til en hastighet opp til å gjøre din boble slags kjøre litt fortere . På hver pass, har et flagg som blir satt til true bare hvis du faktisk slå to tall. Før du gjør det neste pass, sjekk for å se om flagget er sann eller usann . Hvis det er sant , byttet du to tall, og du må gjøre et annet pass. Hvis det er falsk , er listen sortert, og du kan gjøres. I vårt eksempel , selv om listen ble sortert etter 3 pasninger , ville vi fortsatt trenger å gjøre en fjerde pass fordi vi har gjort et bytte i tredje pass.
9

Nå vet du hvordan du gjør en boble slag. Kommentarfunksjonen med eventuelle spørsmål du måtte ha. Takk for lesing!