Bubble sort is a relatively dumb algorithm, which is in fact only used in the
academic world. It has no good properties, however, its process may remind you
of physical or natural phenomena. The algorithm works in waves, wherein each
wave it drops the "heaviest" item over to the end or sends the
lightest bubbles to the top (depending on the implementation). Each wave
compares a pair of neighboring items. If the left item is bigger than the right
one, it swaps the items. Thanks to this, the algorithm is stable.
Possible improvements
The algorithm can be written in a completely stupid way using two nested for
loops with a fixed number of iterations (both would run as many times as the
items in the array). However, if we think about it a little we'd find out that
it's pointless to compare the heaviest items at the "bottom" of the array
because they already are in the right place. With this in mind, we can shorten
the waves by 1 item continuously and even skip the very last one.
Another improvement might be to check if the array is already sorted (this
can easily happen). For example, imagine that we have a loop running and we no
longer need to sort it. We can easily set up a variable named
swapped to false and set this variable to
true after each swap. If we get to the end of the loop and we
didn't swap anything (the variable has a value of false), then we
know we're done. Those two improvements are shown in the preview in the source
code below.
The best possible implementation of this "bubbling" algorithm is called
bi-directional bubble sort (or Shaker sort or Cocktail sort). There, it runs 2
waves in each run of the nested loop - one from left to right pushing heavier
items down and another from the right pulling lighter items up. This removes the
problem of so-called rabbits and turtles where rabbits are heavy items which
quickly drop down. However, in the original implementation, lighter items come
up very slowly.
Algorithm properties
Time complexity
O (n2)
Stability
Yes
Speed
Very bad
Note: the time complexity is meant for average cases, and the speed is
like this when compared to all other sorting algorithms.
Process
Since Bubble sort is not an optimized algorithm, its process will be bit
longer.
We have an array of the following items:
3
2
5
1
9
4
The first wave will go through the entire array and the greatest item will
"bubble" over to the end.
3
2
5
1
9
4
Let's start up on the wave and compare the first 2 items (3 and 2):
3
2
5
1
9
4
Three is greater than two so we swap those items:
2
3
5
1
9
4
Then, we compare two more of the items (3 and 5):
2
3
5
1
9
4
Those are in the correct order, so we don't swap them. The wave
continues...
2
3
5
1
9
4
2
3
1
5
9
4
2
3
1
5
9
4
2
3
1
5
4
9
After the first wave, the maximum (9) had bubbled up to the end, as expected.
The last item is sorted in and we no longer have to deal with it. The next wave
will be one item shorter than the previous wave and it'll bring the largest out
of the array's unsorted parts to the end.
2
3
1
5
4
9
2
3
1
5
4
9
2
1
3
5
4
9
2
1
3
5
4
9
2
1
3
4
5
9
After the second wave, we're left with two sorted items at the end of the
array. Let's do another wave.
2
1
3
4
5
9
1
2
3
4
5
9
1
2
3
4
5
9
1
2
3
4
5
9
Now, the array has been completely sorted. Realistically, the program would
do one more wave before finding out that there is nothing to swap and return the
result.
Visualization
The author of the visualization widget is Jenkings
// sorts the array, assumes indexing from 0
procedure bubble_sort(var list: array of integer);
var i, j, temp: integer;
swapped: boolean;
begin
j:=length(list) - 2;
// swap check
swapped:=true;
while swapped do begin
swapped:=false;
for i:=0 to j do// swap itemsif (list[i] > list[i + 1]) then begin
temp:=list[i];
list[i]:=list[i + 1];
list[i + 1]:=temp;
swapped:=true;
end;
dec(j);
end;
end;
# returns sorted arraydef bubble_sort(list)
j = list.length - 2# swap check
swapped = true
while (swapped) do
swapped = false
(j + 1).times do |i|
# swapif (list[i] > list[i + 1])
temp = list[i]
list[i] = list[i + 1]
list[i + 1] = temp
swapped = true
end
end
j -= 1
end
end