# sorting by direct insertion

# Nach Eingabe einer natuerlichen Zahl n und der
# Zuweisung von Zufallszahlen an die n Komponenten
# des Arrays a wird das Array a sortiert.

# Das Einfügen des ersten Elements a[j] der unsortierten
# Teilliste a[j],...,a[n-1] in die bereits sortierte Teilliste
# a[0],...,a[j-1] wird an eine Funktion mit dem Namen "insert"
# und dem Parameter "x" delegiert.

from random import randint
import time

n = int(input('Anzahl der Datenelemente = '))
r = int(input('Wieviele Elemente sollen angezeigt werden? '))

# Erzeugen des arrays mit dem Namen a 
# und den n Komponenten a[0], . . . , a[n-1]
a = list(range(0,n))

# Zuweisung von Zufallszahlen an die Komponenten der Liste a
for i in range(0,n):  a[i]= randint(1,999999)

# Ausgabe der Quelliste
print()
print('Quelliste:')
for i in range(0,r): print(a[i])

# Implementierung der Funktion "insert"

def insert(x):
   current = a[x]
   i = x - 1
   while i >= 0 and current < a[i]:
           a[i+1] = a[i]
           a[i]   = current
           i = i - 1
  
  
start = time.time()

j = 1
while j <= n - 1:
  insert(j)
  j += 1

end = time.time()

# Ausgabe der sortierten Liste
print()
print('sortierte Liste:')
for i in range(0,r): print(a[i])

print()
print('Zeitaufwand zum Sortieren von',n,'Elementen: {:7.3f} s'.format(end-start))