## Bubble sort

Algorithms 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 repetitions (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 most difficult items at the "bottom" of 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 actually 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 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 Bubble sort with shaker (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 (n^{2}) |
---|---|

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 biggest 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 bigger 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

### 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
```

**Comments**

Nobody has commented yet - be the first!