#a = [4, 2, 5, 3]
a = [4, 3, 9, 2, 7, 1, 6, 8, 5]

print('Niz na početku:', end=' ')
print(a)

#n = 9 je broj elemenata niza
n = len(a)

# sortirani podniz dužine 1 sadrži samo početni element (indeks 0)

# pozicija sledećeg elementa kome treba da nađemo mesto
i = 1

#ponavljamo postupak za sve preostale elemente niza kojima treba naći mesto
while i < n: # while i < 9:
    #trenutna pozicija elementa koji raspoređujemo, kome tražimo mesto
	j = i
    # sve dok nismo stigli do početka niza
	# i dok je umetnuti element manji od prethodnog elementa, 
	# pomeramo ga ulevo
    while j > 0 and a[j] < a[j - 1]:
        #zamena
        temp = a[j] 
        a[j] = a[j - 1]
        a[j - 1] = temp
        #zamena u Python-u: a[j], a[j - 1] = a[j - 1], a[j]
        j -= 1
    i += 1
    
print('Niz na kraju:', end=' ')
print(a)