Sortare prin insertie (Insertion sort)

Pentru realizarea sortarii prin insertie, ideea de baza este inserarea unui anumit element in sirul deja sortat al predecesorilor sai.

De exemplu, fie un sir nesortat: 3, 14, 8, 4, 21, 16 si vrem sa-l sortam crescator.
Se pastreaza primul element 3 considerandu-se un subsir deja sortat. Apoi se trece la 14, caruia ii cautam locul in subsir, observam ca 3 mai mic decat 14, si deci subsirul este sortat (3, 14, 8, 4, 21, 16). Trecem la 8, ii cautam locul in subsir. 8 mai mare decat 3, cautam locul in continuare. 8 mai mic decat 14, si deci 8 se va afla inainte de 14. Tot ceea ce facem mai departe este sa il inseram in acea pozitie, elementele care urmeaza dupa el mutandu-se la dreapta cu o pozitie (3, 8, 14, 4, 21, 16). Procedeul se repeta pana cand intreg vectorul ajunge sortat.

Algoritmul in Python este urmatorul :

import random

n = eval(input("Enter how many numbers.. "))
arr = []
for i in range (n):
    nr = random.randint(0,100)
    arr.append(nr)

print("Initial array array: ", end=" ")
for i in range (n):
    print (arr[i], end = " ")
print()

for i in range (1,n):
    key = arr[i]
    j = i-1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = key

print("Sorted array: ", end=" ")
for i in range (n):
    print (arr[i], end = " ")
print()