exchange sort: the simplest sorting algorithm

exchange_sort.py

# https://arxiv.org/pdf/2110.01111.pdf

def exchange_sort(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if A[i] > A[j]:
                A[i], A[j] = A[j], A[i]

def exchange_sort_improved(A):
    for i in range(1, len(A)):
        for j in range(i):
            if A[i] < A[j]:
                A[i], A[j] = A[j], A[i]

if __name__ == "__main__":
    from random import randint, shuffle

    for _ in range(100000):
        A = [randint(0, 100) for _ in range(randint(0, 100))]
        shuffle(A)
        AA, AAA, AAAA = A[:], A[:], A[:]
        exchange_sort_improved(AA)
        exchange_sort(AAA)
        AAAA.sort()
        assert AA == AAA == AAAA