Bubble Sort

This is the Bubble Sort algorithm. It is one of the most least efficient in time complexity, but it's effervescent name keeps people coming back.
The algorithm, which falls under the "comparison sort" paradigm, works by repeatedly stepping through the array, comparing adjacent elements, and swapping elements that are out of order. The first pass through the array starts by comparing the first and second values, then the second and third, then the third and fourth, ..., then the next-to-last and last, and will result in the largest element at the end of the array; i.e., the array is partially sorted in the last element. The second pass compares the second and third, the third and fourth, ... , then the next-next-to-last and the next-to-last element; since the last element was placed in the correct place in the first pass, it no longer needs to be checked.

def bubble_sort(lst):
 for i in range(len(lst)-1,0,-1):
  for j in range(i):
   if lst[j] > lst[j+1]:
    lst[j], lst[j+1] = lst[j+1], lst[j]

The naive Bubble sort implementation above provides best case $\Omega(n^2)$ and worst case $O(n^2)$, giving $\Theta(n^2)$ in time complexity.
Optimized versions of Bubble sort, like the one below, provide best case $\Omega(n)$ and worst case $O(n^2)$. The $\Omega(n)$ best case occurs when the list is already in sorted order. A boolean flag is set to $0$, and the loops runs more or less the same as in the naive algorithm, with the exception that if, in any loop, no two elements are swapped, then the list is in sorted order and the $while$ loop terminates.

def bubble_sort2(lst):
 swapped = False
 n = len(lst)
 while not swapped:
  swapped = False
  for i in range(n):
   if lst[i] < lst[i+1]:
    swap(lst, i, j)
    swapped = True
  n -= 1

The following version of Bubble sort is more efficient than the first two. It takes advantage of the fact that the index of the last swap is the position beyond which the array is sorted, because if it were not sorted, there would have been a swap. If the array is already in sorted order, the algorithm will make one pass over the $n-1$ pairs of adjacent elements, and then terminate, giving best case $\Omega(n)$ and worst case $O(n^2)$ if the list of reverse sorted.

def bubble_sort3(lst):
 n = len(lst)
 while n > 0:
  new_n = 0
  for i in range(1, n):
   if lst[i-1] > lst[i]:
    lst[i-1], lst[i] = lst[i], lst[i-1]
    new_n = i
  n = new_n