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

def selection_sort(a):
    n = len(a)
    
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if a[min_index] > a[j]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]