#insertion_sort - sortowanie przez wstawianie
#www.algorytm.org

import pytest, random

def insertion_sort(data):
    #dla kolejnych elementow
    for i in range(1, len(data)): 
        key = data[i]
        j = 0
        #poszukaj miejsce gdzie wstawic aktualny element
        while key > data[j] and j<i:
            j += 1
        data.insert(j, key) #wstaw element w znalezione miejsce
        del data[i+1] #usun element - wstawilismy element na miejsce (stworzylismy jego kopie, usun oryginal)
    
    
def test_sort_random():
    for i in range(500):
        x = [random.randint(0,1000) for i in range(1000)]
        insertion_sort(x)
    assert True