Hvordan gjøre en boble slags
Boblesortering er en av de enkleste sorteringsalgoritmer. Det kalles boblesortering fordi det vil "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æringsformål (med mindre du kjenner din liste er nesten sortert, i så fall er det ikke ille)
Bruksanvisning
1 Jeg tror den beste måten å diskutere boblesortering 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 Boblesortering 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 (dvs. 1,2,3 osv.). Den slags virker ved å passere over hvert element i listen og sammenligne det til neste element i listen. Dersom det første elementet er større enn det andre elementet, er de to byttet om. Dersom det første elementet er mindre enn eller lik den andre, skjer ingenting. Etter å se på dette elementet, er det neste elementet sett på, og prosessen gjentas.
3 Når typen har sett på hvert element, har en 'pass' fullført. Etter ett pass, vet du sikkert at ett nummer må være i riktig posisjon. I vår stigende rekkefølge, den største verdien vil "boble" til enden 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 slutt siden du vet at nummeret er allerede i riktig posisjon.
4 Boblesortering (vanligvis) krever flere omganger for å fullføre. Den mest passerer det vil kreve er lik antall elementer i listen minus 1. Så hvis du har 10 elementer i listen, kan det ta 9 passerer å fullføre sorter. 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 at listen for å se slik ut:
1, 2, 3, 4, 6, 8
På den første pass, vil vi sammenligne tallene en om gangen, og vi vet at etter en pasning bør vi ha flest helt til høyre, så i dette tilfellet vil det være 8. For vårt eksempel, den ^ tegnet vil peke på plass 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 vil bytte dem.
3, ^ 6, 1, 8, 2, 4-
Pass 1, trinn 2) Sammenlign 6 og 1. 6 er større enn 1, så vi vil bytte dem.
3, 1, ^ 6, 8, 2, 4-
Bestå 1, trinn 3) Sammenlign 6 og 8. 6 er mindre enn eller lik 8, slik at det ikke skjer.
3, 1, 6, ^ 8, 2, 4-
Bestå 1, trinn 4) Sammenlign 8 og 2. 8 er større enn 2, så bytte dem.
3, 1, 6, 2, ^ 8, 4
Bestå 1, trinn 5) Sammenlign 8 og 4. 8 er større enn 4, slik at bytte dem.
3, 1, 6, 2, 4, 8
Og du er ferdig første pass!
7 3, 1, 6, 2, 4, 8 knapt 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 matcher mine:
Pass 2: 1, 3, 2, 4, 6, 8 (ser bedre)
Bestå 3: 1, 2, 3, 4, 6, 8 (ferdig)
Pass 4: 1, 2, 3, 4, 6, 8 (umm ... ikke var vi allerede gjort?)
Pass 5: 1, 2, 3, 4, 6, 8 (fortsatt gjøres!)
8 Som du kan se, ble listen sortert etter 3 passerer, men boblesortering holdt det gående. Hvorfor det? Vel, er den grunnleggende boblesortering 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 ditt boblesortering kjøre litt fortere. På hver pass, har et flagg som blir satt til sann bare hvis du faktisk bytte to tall. Før du gjør det neste pass, sjekk for å se om flagget er sant eller usant. Hvis det er sant, byttet du to tall, og du må gjøre en annen pass. Hvis det er falsk, er listen sortert, og du kan gjøres. I vårt eksempel, selv om listen ble sortert etter 3 passerer, 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 boblesortering. Legge inn kommentarer med spørsmål du måtte ha. Takk for at du leste!
Hint
- Hvis du prøver å implementere boblesortering i et programmeringsspråk, og du har problemer, kan en blyant og papir hjelpe deg å visualisere hva algoritmen prøver å gjøre
- Husk, boblesortering er ikke en veldig effektiv form. Så hvis du trenger å sortere en stor liste, bør du se til noen andre metoder.