- Sammenlignet
- Byttet
- På plads
Boblesortering
Boblesortering gennemgår en liste igen og igen, sammenligner hvert par naboer og bytter dem, når den venstre er størst. Efter hvert gennemløb er den største værdi, der endnu ikke står på plads, boblet op til enden. Afspil sorteringen i den hastighed, du vil, eller gå igennem den én sammenligning ad gangen, og følg tællerne for sammenligninger, ombytninger og gennemløb. Tryk på Afspil for at se sorteringen, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Felterne tæller sammenligninger, ombytninger og gennemløb. Vælg hvor mange søjler, hvordan de starter, eller skriv dine egne tal. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.
Sådan virker det
- Vælg hvor mange søjler og hvordan de starter: tilfældigt, næsten sorteret, omvendt eller med få unikke værdier. Eller skriv dine egne tal.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i sorteringen.
- Se felterne tælle sammenligninger, ombytninger og gennemløb, og sammenlign dem med det værste tilfælde.
Sådan virker boblesortering
Start til venstre. Sammenlign de to første værdier; er den venstre størst, så byt dem. Ryk én plads til højre og sammenlign igen, helt til enden af listen. Det er ét gennemløb, og bagefter står den største værdi på sidste plads. Næste gennemløb stopper én plads tidligere. Fortsæt, til et gennemløb ikke bytter noget, eller til der kun er én værdi tilbage.
Arbejdet talt op
For n værdier laver første gennemløb n − 1 sammenligninger, det næste n − 2 og så videre, så en hel sortering laver højst n(n − 1)/2 sammenligninger. Antallet af ombytninger er altid antallet af inversioner i startlisten: par af værdier, der står i forkert rækkefølge. En omvendt liste har flest, n(n − 1)/2. En sorteret liste har ingen, og med tidligt stop tager den ét gennemløb med n − 1 sammenligninger.
Ofte stillede spørgsmål
Hvorfor hedder det boblesortering?
Fordi store værdier stiger op til enden af listen som bobler i vand. I hvert gennemløb rykker den største værdi, der endnu ikke står på plads, trin for trin mod højre, til den når sin endelige plads.
Hvor mange sammenligninger og ombytninger laver boblesortering?
Højst n(n − 1)/2 sammenligninger for n værdier: 45 for 10 værdier, 780 for 40. Antallet af ombytninger er altid lig med antallet af inversioner i startlisten, fra ingen for en sorteret liste til n(n − 1)/2 for en omvendt.
Hvad gør tidligt stop?
Hvis et helt gennemløb ikke bytter noget, står alle par af naboer i rækkefølge, så listen er sorteret, og sorteringen kan stoppe. Med tidligt stop slået til tager en sorteret liste ét gennemløb. Uden laver boblesortering altid alle n − 1 gennemløb.
Bruges boblesortering i praksis?
Sjældent. Den er enkel og stabil, men bruger i gennemsnit tid proportional med n². Indsættelsessortering gør det samme med færre trin på små eller næsten sorterede lister, og flettesortering eller quicksort er meget hurtigere på store.
Bliver mine tal sendt nogen steder hen?
Nej. Sorteringen kører i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor