Bubble sort

Bubble sort is the simplest exchange sorting algorithm.

Each element of the array is compared with its subsequent element of the array and swapped if bigger until the end of the array. As after the first pass, the maximum element of the array is in the end, the comparison process can stop one element before the end of the array.

The worst-case and average complexity is O(n²).

This algorithm should only be used on almost sorted array (that implies few permutations).

This algorithm has one advantage in its ability to tell if an array is already sorted in O(n).

Resources

https://en.wikipedia.org/wiki/Bubble_sort