Vergelijkingen
Verwisselingen
Ronde

  • Vergeleken
  • Verwisseld
  • Op zijn plek

Meer over bubblesort

Bubblesort

Bubblesort loopt steeds opnieuw door een lijst, vergelijkt elk paar buren en verwisselt ze als de linker groter is. Na elke ronde is de grootste waarde die nog niet op zijn plek stond naar het eind geborreld. Speel het sorteren af op elke snelheid, of loop er per vergelijking doorheen, en volg de tellers voor vergelijkingen, verwisselingen en rondes. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om ergens naartoe te springen. De tegels tellen vergelijkingen, verwisselingen en rondes. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.

Hoe het werkt

  1. Kies hoeveel staven en hoe ze beginnen: willekeurig, bijna gesorteerd, omgekeerd of met weinig unieke waarden. Of typ je eigen getallen.
  2. Druk op Afspelen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
  3. Zie hoe de tegels vergelijkingen, verwisselingen en rondes tellen, en vergelijk ze met het slechtste geval.

Zo werkt bubblesort

Begin links. Vergelijk de eerste twee waarden; is de linker groter, verwissel ze dan. Schuif één plek naar rechts en vergelijk opnieuw, tot het eind van de lijst. Dat is één ronde, en daarna staat de grootste waarde op de laatste plek. De volgende ronde stopt één plek eerder. Ga door tot een ronde niets verwisselt, of tot er nog maar één waarde over is.

Het werk tellen

Bij n waarden doet de eerste ronde n − 1 vergelijkingen, de volgende n − 2, enzovoort, dus een volledige sortering kost hoogstens n(n − 1)/2 vergelijkingen. Het aantal verwisselingen is altijd het aantal inversies in de beginlijst: paren waarden die in de verkeerde volgorde staan. Een omgekeerde lijst heeft er de meeste, n(n − 1)/2. Een gesorteerde lijst heeft er geen, en met de vroege stop kost die één ronde van n − 1 vergelijkingen.

Veelgestelde vragen

Waarom heet het bubblesort?

Omdat grote waarden naar het eind van de lijst stijgen, zoals bellen in water. In elke ronde schuift de grootste waarde die nog niet op zijn plek staat stap voor stap naar rechts, tot hij op zijn definitieve plek staat.

Hoeveel vergelijkingen en verwisselingen doet bubblesort?

Hoogstens n(n − 1)/2 vergelijkingen bij n waarden: 45 bij 10 waarden, 780 bij 40. Het aantal verwisselingen is altijd gelijk aan het aantal inversies in de beginlijst, van nul bij een gesorteerde lijst tot n(n − 1)/2 bij een omgekeerde.

Wat doet de vroege stop?

Als een hele ronde niets verwisselt, staat elk paar buren op volgorde. De lijst is dan gesorteerd en het sorteren kan stoppen. Met de vroege stop aan kost een gesorteerde lijst één ronde. Staat hij uit, dan doet bubblesort altijd alle n − 1 rondes.

Wordt bubblesort in de praktijk gebruikt?

Zelden. Het is eenvoudig en stabiel, maar kost gemiddeld tijd evenredig met n². Insertion sort doet hetzelfde met minder stappen op korte of bijna gesorteerde lijsten, en merge sort of quicksort zijn veel sneller op lange lijsten.

Worden mijn getallen ergens naartoe gestuurd?

Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor