Bubble sort

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

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:

The first wave will go through the entire array and the greatest item will "bubble" over to the end.

Let's start up on the wave and compare the first 2 items (3 and 2):

Three is greater than two so we swap those items:

Then, we compare two more of the items (3 and 5):

Those are in the correct order, so we don't swap them. The wave continues...

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.

After the second wave, we're left with two sorted items at the end of the array. Let's do another wave.

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

Source code

public static void bubbleSort(int[] list) {
  int j = list.length - 2, temp;
  // swap check
  boolean swapped = true;
  while (swapped) {
    swapped = false;
    for (int i = 0; i <= j; i++) {
      // swapping
      if (list[i] > list[i + 1]) {
        temp = list[i];
        list[i] = list[i + 1];
        list[i + 1] = temp;
        swapped = true;
      }
    }
    j--;
  }
}

public static void bubbleSort(int[] list) {
  int j = list.Length - 2, temp;
  // swap check
  bool swapped = true;
  while (swapped) {
    swapped = false;
    for (int i = 0; i <= j; i++) {
      // swap
      if (list[i] > list[i + 1]) {
        temp = list[i];
        list[i] = list[i + 1];
        list[i + 1] = temp;
        swapped = true;
      }
    }
    j--;
  }
}

// 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 items
      if (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 array
def bubble_sort(list)
   j = list.length - 2
   # swap check
   swapped = true
   while (swapped) do
     swapped = false
     (j + 1).times do |i|
       # swap
       if (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