Bubble sort

Bubble sort owes its name to the fact that the largest values gradually « rise » toward the end of the array, like bubbles rising to the surface. The principle is simple: you scan the array and compare each pair of neighboring elements; if they are in the wrong order, you swap them. You repeat this pass until no more swaps are needed.

At each full pass, the largest remaining element necessarily rises up to its final position, on the right. That is why the zone to scan can be reduced by one notch at each pass.

start   : [5, 2, 4, 1, 3]
pass 0  : [2, 4, 1, 3, 5]   (5 rises all the way to the right)
pass 1  : [2, 1, 3, 4, 5]   (4 settles just before 5)
pass 2  : [1, 2, 3, 4, 5]   (3 settles just before 4)
pass 3  : [1, 2, 3, 4, 5]   (no swap -> array already sorted, we stop)

The complexity is O(n²) in the worst case (array sorted in reverse) because each pass compares almost the whole array, and almost n passes are needed. But with a small flag (« did we make a swap? »), bubble sort becomes O(n) in the best case: if no swap happens during a pass, the array is already sorted and we can stop immediately.

def tri_bulles(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        echange = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                echange = True
        if not echange:
            break
    return a

Classic pitfall: forgetting to reduce the bound n - 1 - i (you must not recheck the part already sorted on the right), and forgetting the echange flag, which makes the algorithm much slower on nearly-sorted arrays.