from random import randint;

# Implementatie van sorteren door invoegen
def sorteer(lijst):
    for lengte in range(1, len(lijst)):   # lengte van het groene deel
        getal = lijst[lengte]             # gele getal
        # bijna letterlijke kopie van invoegen(…)
        index = lengte - 1
        while index >= 0 and lijst[index] > getal:
            lijst[index + 1] = lijst[index]
            index -= 1
        lijst[index + 1] = getal


lijst = [7, 4, 9, 5, 2, 6]
sorteer(lijst)
print(lijst)

lijst = [9, 8, 7, 6, 5, 4, 3, 2, 1]
sorteer(lijst)
print(lijst)

lijst = list(range(15))
sorteer(lijst)
print(lijst)

lijst = [7]
sorteer(lijst)
print(lijst)

lijst = []
sorteer(lijst)
print(lijst)


def is_gesorteerd(lijst):
    index = 1;
    while index < len(lijst) and lijst[index - 1] <= lijst[index]:
        index += 1
    return index >= len(lijst)

for _ in range(1000):
    # een willekeurige lijst van 20 gehele getallen in het bereik [0,30]
    lijst = []
    for _ in range(20):
        lijst.append(randint(0, 30))
    sorteer(lijst)
    if not is_gesorteerd(lijst):
        print ("Niet gesorteerd:", lijst)