# Sortieren durch direkte Auswahl
# Complexity: O(n^2)

import time
from random import randint

def sort_direct_insertion(array):
    for i in range(1,len(array)):
        helpvariable = array[i]
        j = i-1
        while j >= 0 and array[j] > helpvariable:
            array[j+1] = array[j]
            j = j-1
            array[j+1] = helpvariable
    return array
 
n=int(input("n = "))
n=n+1
a=list(range(1,n+1))
print()
print('zu sortierende Liste:')
for i in range (1,n):
    a[i]=randint(1,1000000)
for i in range (1,4):
    print(a[i])
print()
print('sortierte Liste:')



start = time.time()

sort_direct_insertion(a)

end = time.time()

for i in range (1,4):
    print(a[i])
print()
print('Zeit sort_direct_insertion: {:5.3f} s'.format(end-start),'bei', n-1,'Datenelementen')