|Worst-case performance||О(n²) comparisons, О(n²) swaps|
|Best-case performance||О(n) comparisons, О(1) swaps|
|Average performance||О(n²) comparisons, О(n²) swaps|
|Worst-case space complexity||O(1) auxiliary|
A bubble sort, a sorting algorithm that continuously steps through a list, swapping items until they appear in the correct order. The list was plotted in a Cartesian coordinate system, with each point (x, y) indicating that the value y is stored at index x. Then the list would be sorted by bubble sort according to every pixel’s value. Note that the largest end gets sorted first, with smaller elements taking longer to move to their correct positions.
An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.