from time import time
from random import randint as ri

testlist = []

for i in range(1000):
    testlist.append(ri(1,10000))

def puzirk(lst):
    start = time()
    for i in range(len(lst)):
        for j in range(len(lst)-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    end = time()
    return end - start

def smng(lst):
    start = time()
    b = []
    a = []
    for i in range(max(testlist)):
        a.append(0)
    for i in lst:
        a[i-1] += 1
    k = 1
    for i in a:
        for j in range(i):
            b.append(k)
    k += 1
    end = time()
    return end - start

def porazrad(lst):
    start = time()
    length = len(str(max(lst)))
    for i in range(length):
        B = [[] for k in range(10)]
        for x in lst:
            figure = x // 10**i % 10
            B[figure].append(x)
        lst = []
        for k in range(10):
            lst += B[k]
    end = time()
    return end - start

print(puzirk(testlist), smng(testlist), porazrad(testlist), sep='\n')