Bubblesort

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Bubblesort

Bubblesort (= exchangeSort) is een sorteeralgoritme. Het wordt vaak gebruikt als illustratie van een algoritme. Voor echte toepassing in programma's bestaan veel betere methoden en is bubblesort beslist af te raden.

Werking[bewerken]

Een voorbeeld van bubble sort. Startend vanaf het begin van de rij, vergelijk ieder aan elkaar grenzend tweetal getallen, verwissel ze als het linker getal groter is dan het rechter en schuif dan één positie door. Na het afwerken van de hele rij is er bij de volgende herhaling één element minder om te sorteren omdat het laatste getal dan zeker het hoogste is.

Bubblesort werkt als volgt:

  • 1. Loop door de te sorteren rij van n elementen en vergelijk elk element met het volgende. Verwissel beide als ze in de verkeerde volgorde staan. Schuif dan een stapje op.
  • 2. Loop opnieuw door de rij, maar ga nu door tot het voorlaatste element, omdat het laatste element het grootste in de rij was.
  • 3. Nog een keer, maar negeer dan de twee laatste elementen.
  • 4. Ga zo door.
  • n. Nog een keer, maar negeer dan de laatste n-1 getallen.
  • n+1. Klaar.

We zien de grotere elementen als het ware als luchtbellen naar boven drijven. Aan deze metafoor ontleent het algoritme zijn naam.

Bubblesort is, met een grootteorde \mathcal{O}(n^2), vrij inefficiënt.

Als je voor elke keer dat je door de lijst loopt bijhoudt hoeveel verwisselingen worden gemaakt, is het mogelijk om vroegtijdig te stoppen zodra er geen verwisselingen meer nodig zijn. Dit kan in praktische zin een verbetering opleveren ten opzichte van de theoretische looptijd van het bubblesortalgoritme.

Implementaties[bewerken]

Implementatie in Visual Basic 6[bewerken]

 Private SUB Form_Click()
     DIM i AS INTEGER
     DIM v AS Boolean
     DIM j AS INTEGER
     DIM temp AS INTEGER
     DIM arr(4) AS INTEGER
 
     arr(1) = 31
     arr(2) = 2252
     arr(3) = 12
     arr(4) = 41
 
     i = 1
     v = True
     DO WHILE i < 4 AND v = True
         v = False
         j = 1
         DO WHILE j <= 4 - i
             IF arr(j) > arr(j + 1) THEN
                 temp = arr(j)
                 arr(j) = arr(j + 1)
                 arr(j + 1) = temp
                 v = True
             END IF
             j = j + 1
         LOOP
         i = i + 1
     LOOP
     Me.CLS
     FOR i = 1 TO 4
         PRINT arr(i)
     NEXT i
 END SUB

Implementatie in PHP[bewerken]

 <?php
 $v = true;
 $Arr = array (31,56,8,211);
 $Count = count ($Arr) - 1;
 for ($i = 0; ($i < $Count) && ($v == True); $i++)
 {
     $v = false;
     for ($j = 0; $j < ($Count - $i); $j++)
     {
         if ($Arr[$j] > $Arr[$j + 1])
         {
             $Temp = $Arr[$j];
             $Arr[$j] = $Arr[$j + 1];
             $Arr[$j + 1] = $Temp;
             $v = true;
         }
     }
 }
 print_r ($Arr);
 ?>

Implementatie in Java[bewerken]

 public int[] bubbleSort(int invoer[]) {
    int i, j, tijdelijk;
    for (j = 0; j < invoer.length; j++) {
       for (i = 1; i < invoer.length - j; i++) {
          if(invoer[i-1] > invoer[i]) {
             tijdelijk = invoer[i];
             invoer[i] = invoer[i-1];
             invoer[i-1] = tijdelijk;
          }
       }
    }
return invoer;
 }

Implementatie in C[bewerken]

"Invoer" is de te sorteren array, "lengte" is het aantal elementen in de array.

 void bubblesort(int invoer[], int lengte) {
    int i, j, tijdelijk;
    for (j = 0; j < lengte; j++) {
       for (i = 1; i < lengte - j; i++) {
          if(invoer[i-1] > invoer[i]) {
             tijdelijk = invoer[i];
             invoer[i] = invoer[i-1];
             invoer[i-1] = tijdelijk;
          }
       }
    }
 }

Implementatie in MATLAB[bewerken]

"x" is de te sorteren array.

 tijdelijk = 0; 
 for j=1:length(x),
  for i=1:length(x)-j,
    if x(i) > x(i+1), 
      tijdelijk = x(i+1); 
      x(i+1)=x(i); 
      x(i)=tijdelijk; 
    end
  end
 end

Implementatie in C# (Csharp)[bewerken]

public void BubbleSort(int[] T)
{
  int X;
  for (int I = T.Length -1; I >= 1; I--)
  {
    for (int J = 0; J < T.Length - 1; J++)
    {
      if(T[J] > T[J+1])
      {
        X = T[J];      // bijhouden inhoud van T[J]
        T[J] = T[J+1]; // inhoud van T[J] wordt de kleinere inhoud van T[J+1]
        T[J+1] = X;    // inhoud van T[J+1] wordt de grotere inhoud van de oorspronkelijke T[J] of dus X 
      }
    }
  }
}/*BubbleSort*/

Implementatie in Python[bewerken]

Iteratieve implementatie[bewerken]

rij is de te sorteren rij.
Twee for-lussen kan ook, zoals uitvoerig geïllustreerd in de andere programmeertalen.

def bubblesort(rij):
    while True:                       #Oneindige lus
        verwisseld = False
        for i in range(len(rij)-1):
            if rij[i] > rij[i+1]:
                rij[i], rij[i+1] = rij[i+1], rij[i] #swap
                verwisseld = True
        if not verwisseld:            #Beïndig lus als alles op de correcte plaats staat
            break

Iteratief voorbeeld[bewerken]

Hier sorteren we een willekeurig rij van woorden, met telkens de vermelding welke twee opeenvolgende woorden worden verwisseld (i.e. swap).

['doek', 'groen', 'ezel', 'fiets', 'appel', 'boom', 'citroen']
 swap(groen,ezel) swap(groen,fiets) swap(groen,appel) swap(groen,boom) swap(groen,citroen)
 
['doek', 'ezel', 'fiets', 'appel', 'boom', 'citroen', 'groen']
 swap(fiets,appel) swap(fiets,boom) swap(fiets,citroen)
 
['doek', 'ezel', 'appel', 'boom', 'citroen', 'fiets', 'groen']
 swap(ezel,appel) swap(ezel,boom) swap(ezel,citroen)
 
['doek', 'appel', 'boom', 'citroen', 'ezel', 'fiets', 'groen']
 swap(doek,appel) swap(doek,boom) swap(doek,citroen)
 
['appel', 'boom', 'citroen', 'doek', 'ezel', 'fiets', 'groen']

Recursieve implementatie[bewerken]

Bubblesort heeft de interessante eigenschap dat bij elke stap de grootste waarde uit het ongesorteerde deel naar achter 'bubbelt'. Het 'naar achter bubbelen' wordt afgehandeld door de functie bubUp. Het bubbelen wordt veroorzaakt door de swap (het verwisselen van twee elementen). rij[:1] geeft ons een lijst met enkel het eerste element. rij[1:] geeft ons een lijst met alle daaropvolgende elementen. Op deze laatste voeren we recursief weer bubUp uit. Zo verkleinen we stelselmatig onze rij, tot er slechts een element in onze rij zit, namelijk het grootste.

De functie bub laat, via bubUp, de grootste naar achter bubbelen, popt deze laatste (grootste) van de rij af en gaat verder met de rij zonder dat laatste element, totdat er slechts één element in de rij zit, namelijk het kleinste element uit de oorspronkelijke rij.

def bubblesort(rij):
    def bub(rij):
        if len(rij)<=1:               #Stopconditie bub
            return rij
        else:
            rij = bubUp(rij)          #Laat de grootste naar achter bubbelen (en sorteer ietwat)
            laatste = [rij.pop()]     #Verwijder de grootste
            return bub(rij)+laatste   #Recursieve aanroep
    def bubUp(rij):
        if len(rij)<=1:               #Stopconditie bubUp
            return rij
        else:
            if rij[0] > rij[1]:
                rij[0], rij[1] = rij[1], rij[0]  #Verwissel de eerste met de tweede
            return rij[:1]+bubUp(rij[1:]) #Recursieve aanroep 
    return bub(rij)                   #Startconditie voor bubblesort

Recursief voorbeeld[bewerken]

De output van bovenstaande code op een willekeurige rij.

 ['citroen', 'boom', 'ezel', 'appel', 'doek', 'fiets', 'groen'] pop(['groen'])
 ['boom', 'citroen', 'appel', 'doek', 'ezel', 'fiets'] pop(['fiets'])
 ['boom', 'appel', 'citroen', 'doek', 'ezel'] pop(['ezel'])
 ['appel', 'boom', 'citroen', 'doek'] pop(['doek'])
 ['appel', 'boom', 'citroen'] pop(['citroen'])
 ['appel', 'boom'] pop(['boom'])
 ['appel']
 ['appel', 'boom']
 ['appel', 'boom', 'citroen']
 ['appel', 'boom', 'citroen', 'doek']
 ['appel', 'boom', 'citroen', 'doek', 'ezel']
 ['appel', 'boom', 'citroen', 'doek', 'ezel', 'fiets']
 ['appel', 'boom', 'citroen', 'doek', 'ezel', 'fiets', 'groen']

Zie ook[bewerken]