Bubble Sort

Bubble sort is a really simple sorting algorithm, that has O(n²) time complexity. Its name comes from the fact that, if you would imagine an array to be sorted standing vertically, then (depending on the direction of sorting) the smallest or the biggest values would always bubble up one by one, until the whole array would be sorted.

Let consider an array = [6, 5, 4, 0, -1, -3], then after a first pass, number six would bubble up straight to the end. Our array after the first pass would look like that: [5, 4, 0, -1, -3, 6].

All the other passes would produce the following intermediary results:
 second pass: [4, 0, -1, -3, 5, 6]
 third pass: [0, -1, -3, 4, 5, 6]
forth pass: [-1, -3, 0, 4, 5, 6]

And our final sorted array:
[-3, -1, 0, 4, 5, 6]

As we clearly see each pass is pushing up the biggest value to the top, but just right before the previous biggest value.

Pseudo code for the bubble sort:

for each index in array
  for (each index + 1) in (array - iterations we have already done)
    compare current index and (current index - 1)
    always place the biggest value under current index

Possible implementation in python:

def bubble_sort(array):
    for index1 in range(len(array)):
        for index2 in range(1, len(array) - index1):
            if array[index2 - 1] > array[index2]:
                tmp = array[index2]
                array[index2] = array[index2 - 1]
                array[index2 - 1] = tmp
    
    return array

The embedded loop always decreases the range with each iterations, as we know that the biggest value always lands under the last available index.