Bubblesort
Bubblesort, soms ook exchange sort of sinking sort genoemd, is een eenvoudig sorteeralgoritme. Het is een eenvoudig algoritme, maar inefficiënt. Het wordt vanwege de eenvoud en omdat het gemakkelijk uit te leggen is, vaak gebruikt als illustratie van een algoritme. De naam van het algoritme komt van de analogie met een belletje in een vloeistof dat naar boven drijft, zoals ook de grotere elementen naar de top van de lijst 'drijven'.
Werking
[bewerken | brontekst bewerken]
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 , vrij inefficiënt. De efficiëntste soorteeralgoritmes (zoals bijvoorbeeld mergesort) hebben een complexiteitsgraad van
Als men voor elke keer dat men 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 | brontekst bewerken]Implementatie in Visual Basic 6
[bewerken | brontekst 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 | brontekst 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);
?>
Efficiënte implementatie in PHP
[bewerken | brontekst bewerken]function bubbleSort( &$arr, $asc = true ) {
$iterations = 0;
$len = count( $arr );
$i = 0;
$ordered = false;
$newLen = $len;
while ( !$ordered ) :
$ordered = true;
for ( $i = 1; $i < $len; $i++ ) :
$iterations++;
$a = $arr[ $i - 1 ];
$b = $arr[ $i ];
$comp = (float)( (float)$a - (float)$b );
if ( ( $asc && $comp > 0 ) || ( !$asc && $comp < 0 ) ) :
$arr[ $i - 1 ] = $b;
$arr[ $i ] = $a;
$ordered = false;
$newLen = $i;
endif;
endfor;
$len = $newLen;
endwhile;
return( $iterations );
}
$arr = array( 4, 4, 3, 2, 4, 5, 88, 3, 8448, 43, 2, 0, 480, 334, 1, 0 );
$iterations = bubbleSort( $arr );
echo( "\nIt took " . $iterations . " iterations to sort the array.\n\n" );
print_r( $arr );
Implementatie in Java
[bewerken | brontekst bewerken]public void 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;
}
}
}
}
Implementatie in C
[bewerken | brontekst 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 | brontekst 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 | brontekst 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
}
}
}
}
Implementatie in Python
[bewerken | brontekst bewerken]Iteratieve implementatie
[bewerken | brontekst bewerken]De te sorteren rij wordt ingegeven als parameter.
(Update) Door middel van een offset kunnen we de snelheid van het iteratieve algoritme verhogen.
De lengte van de volgende iteratie wordt namelijk ingekort. Dit komt zowel het ruimtegebruik alsook het tijdsgebruik van de processor ten goede
We weten namelijk dat na elke iteratie over de lijst, het achterste element mag verwijderd worden.
Twee for-lussen gebruiken is ook mogelijk, zoals uitvoerig geïllustreerd in de andere programmeertalen.
def bubblesort(rij):
offset = 1
verwisseld = True
while verwisseld: #Lus terwijl dingen verwisselen
verwisseld = False
for i in range(len(rij)-offset):
if rij[i] > rij[i+1]:
rij[i], rij[i+1] = rij[i+1], rij[i] #swap
verwisseld = True
offset += 1
return rij
Iteratief voorbeeld
[bewerken | brontekst 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']
Iteratief voorbeeld met offset
[bewerken | brontekst bewerken]['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']
swap(fiets,appel) swap(fiets,boom) swap(fiets,citroen)
['doek', 'ezel', 'appel', 'boom', 'citroen']
swap(ezel,appel) swap(ezel,boom) swap(ezel,citroen)
['doek', 'appel', 'boom', 'citroen']
swap(doek,appel) swap(doek,boom) swap(doek,citroen)
['appel', 'boom', 'citroen']
!GEEN SWAPS MEER!
=> return
['appel', 'boom', 'citroen', 'doek', 'ezel', 'fiets', 'groen']
Recursieve implementatie
[bewerken | brontekst 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 | brontekst 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']