- Jämförda
- Bytta
- På plats
Bubbelsortering
Bubbelsortering går igenom en lista om och om igen, jämför varje par grannar och byter plats på dem när den vänstra är större. Efter varje varv har det största värdet som ännu inte står på plats bubblat upp till slutet. Spela sorteringen i valfri hastighet, eller stega igenom den en jämförelse i taget, och följ räknarna för jämförelser, byten och varv. Tryck på Spela för att se sorteringen, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa vart som helst. Rutorna räknar jämförelser, byten och varv. Välj hur många staplar, hur de börjar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Välj antal staplar och startordning: slumpad, nästan sorterad, omvänd eller med få unika värden. Eller skriv dina egna tal.
- Tryck på Spela, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
- Se rutorna räkna jämförelser, byten och varv, och jämför dem med värsta fallet.
Så fungerar bubbelsortering
Börja till vänster. Jämför de två första värdena; om det vänstra är större byter du plats på dem. Flytta ett steg åt höger och jämför igen, ända till slutet av listan. Det är ett varv, och efteråt står det största värdet sist. Nästa varv stannar ett steg tidigare. Fortsätt tills ett varv inte gör några byten, eller tills bara ett värde återstår.
Räkna arbetet
För n värden gör första varvet n − 1 jämförelser, nästa n − 2 och så vidare, så en hel sortering gör högst n(n − 1)/2 jämförelser. Antalet byten är alltid antalet inversioner i startlistan: par av värden som står i fel ordning. En omvänd lista har flest, n(n − 1)/2. En sorterad lista har inga, och med tidigt stopp tar den ett enda varv med n − 1 jämförelser.
Ofta ställda frågor
Varför heter det bubbelsortering?
För att stora värden stiger till slutet av listan som bubblor i vatten. I varje varv flyttas det största värdet som ännu inte står på plats steg för steg åt höger tills det når sin slutliga plats.
Hur många jämförelser och byten gör bubbelsortering?
Högst n(n − 1)/2 jämförelser för n värden: 45 för 10 värden, 780 för 40. Antalet byten är alltid lika med antalet inversioner i startlistan, från inga för en sorterad lista till n(n − 1)/2 för en omvänd.
Vad gör tidigt stopp?
Om ett helt varv inte gör några byten står alla grannpar i ordning, så listan är sorterad och sorteringen kan sluta. Med tidigt stopp påslaget tar en sorterad lista ett varv. Utan det gör bubbelsortering alltid alla n − 1 varv.
Används bubbelsortering i praktiken?
Sällan. Den är enkel och stabil, men tar i genomsnitt tid proportionell mot n². Insättningssortering gör samma jobb med färre steg på små eller nästan sorterade listor, och mergesort eller quicksort är mycket snabbare på stora.
Skickas mina tal någonstans?
Nej. Sorteringen körs i din webbläsare, och dina senaste inställningar sparas i webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor