from time import time


# Dijkstra
def herschik_dijkstra (lijst):   
    # zoek eerste oneven
    index_oneven = 0;
    while index_oneven < len(lijst) and lijst[index_oneven] % 2 == 0:
        index_oneven += 1
    # zoek eerste even
    index_even = index_oneven # kan eventueel nu al + 1
    while index_even < len(lijst) and lijst[index_even] % 2 != 0:
        index_even += 1
    # voor de rest van de lijst werken we element per element
    for i in range(index_even,len(lijst)):
        if lijst[i] % 2 == 0:
            # verwissel
            tmp = lijst[i]
            lijst[i] = lijst[index_oneven]
            lijst[index_oneven] = tmp
            index_oneven += 1
        
        
def herschik (lijst):  #trager
    lijst_oneven =[]
    i = 0
    while i < len(lijst):
        if lijst[i] % 2 != 0:
            element = lijst.pop(i)
            lijst_oneven.append(element)
        else:
            i += 1   
    return lijst + lijst_oneven  #????


# testen - drukt een aantal random lijsten af die herschikt zijn
from random import randint
#traag
totaal = 0

print("Algoritme oef 11.1     Algoritme van Dijkstra")

for _ in range(30):
    lijst = []
    for _ in range (1000):
        lijst.append(randint(0,1000))
    lijst_kopie = lijst.copy()
    
    start = time()
    lijst = herschik(lijst)
    tijd_11_1 = time() - start
    
    start = time()
    lijst = herschik_dijkstra(lijst)
    tijd_dijkstra = time() - start
    
    print(f"{tijd_11_1:.9f}            {tijd_dijkstra:.9f}")