Bubble sort

Bubble sort is one of the simplest and most inefficient sorting algorithms known. It is commonly suggested that bubble sort should only be used for educational purposes.
It is called bubble sort, because smaller elements gradually “bubble” to the top of the list with every iteration. Another, and in my opinion better, name for the algorithm is “sinking sort”, as the largest element sinks to the bottom of the list during every iteration.

How it works

Bubble sort is a comparison sort which works by repeatedly iterating over the list and swapping adjacent elements if the element with the smaller index is larger than the element with the larger index. The list is sorted, when no swap operation was performed during an entire iteration through the list.

During each iteration the biggest element is moved to the end of the list, i.e. it “sinks”. After each iteration, one less element, namely the one that has now sunk to the end has to be considered. This means that after k iterations, the last k elements are in sorted order at the end of the list. This property can be used to optimize the performance of the implementation.

Here is a gif from wikipedia illustrating how bubble sort works.

Code

Here is a naive implementation of bubble sort in python. Note in languages that support do-while loops, that should be used, as there has to be at least one iteration.

 def swap(arr, a, b):  
 arr[a], arr[b] = arr[b], arr[a]
naive bubblesort

The code walks through the list and swaps positions of adjacent elements whenever the element in the lower position has a higher value than the element in the higher position. This is repeatedly done, until not a single swap ocurred during an iteration.

To improve the performance slightly you could take into account the fact that after k iterations the last k elements are sorted and only the first n-k elements need to be compared (This is because during every iteration, the biggest element 'sinks' to the end).

To further optimize the sort you can keep an index at which the last swap occurred during an iteration. All elements at greater indices are guaranteed to already be sorted and need never be checked again in future iterations.

#improved bubblesort
#takes into account the fact that after every for iteration the largest
#value sunk to the end and will not have to ever be checked again.			
def bubblesort2(array):
	wasSwap = True
	end = 1
	while wasSwap:
		wasSwap = False
		for i, key in enumerate(array[:-end]):
			if array[i] > array[i + 1]:
				swap(array, i, i+1)
				wasSwap = True
				end += 1

Complexity

The upper bound time complexity of Bubble Sort is in O(n²). The worst case is if the list is in reverse sorted order, in which case there will be n-1 comparisons and swaps to move the biggest element to the end of the list. Then there are n-2 comparisons and swaps to move the second biggest elements to the second to last position, and so on. So at the k-th iteration there will be n-k comparisons and swaps. Adding it all up we get: n-1 + n-2, … 2, 1. This equals 1/2*(n²-n), which is in O(n²)

In the best case the list is already sorted. In that case there would only be one iteration with n comparisons and no swaps resulting in a time complexity of O(n).

Rabbit, Turtles and Cocktails

One problem with Bubble Sort is that all elements which are not the largest element in the unsorted subarray only move up one spot during each iteration, whereas the largest element always sinks to the bottom within one iteration. Rabbits are large elements at the beginning of the list, as they are rapidly moved towards the end. Turtles are small elements at the end of the list as they slowly move towards the beginning of the list. To increase the speed of rabbits, bubble sort can be modified to work in a bidirectional manner, rapidly moving the largest element to the end during one iteration and then moving the smallest one to the beginning during the next iteration. This sort is called cocktail sort.