from random import randint, choice
from time import time


def swap(m, n):
    tmp = a[m]
    a[m] = a[n]
    a[n] = tmp


def bubble():
    r = len(a)
    was_swap = True
    while (r > 1) and was_swap:
        was_swap = False
        for j in range(0, r - 1):
            if a[j] > a[j + 1]:
                swap(j, j + 1)
                was_swap = True
        r -= 1


def shell():
    n = len(a)
    d = n // 2
    while d > 0:
        for i in range(0, n - d):
            j = i
            while (j >= 0) and (a[j] > a[j + d]):
                swap(j, j + d)
            j -= 1
        d -= 1


def quick(l, r):
    if l >= r: return
    else:
        bar = choice(a[l: r + 1])
        i = l
        j = r
        while i <= j:
            while a[i] < bar: i += 1
            while a[j] > bar: j -= 1
            if i <= j:
                swap(i, j)
                i += 1
                j -= 1
        quick(l, j)
        quick(i, r)


def info():
    t0 = time()
    bubble()
    t1 = time()
    values.append(round(t1 - t0, 5))
    t0 = time()
    shell()
    t1 = time()
    values.append(round(t1 - t0, 5))
    t0 = time()
    quick(0, len(a) - 1)
    t1 = time()
    values.append(round(t1 - t0, 5))


def show(v):
    k = 0
    print('Метод    Отсортированная    Случайная    Обратная')
    for i in range(3):
        print('Метод №', i + 1, '\t\t', v[i], '\t\t', v[i + 3], '\t\t', v[i + 6])


n = int(input("Введите количество элементов в последовательности: "))
values = []
a = [i for i in range(n)]
info()
del a
a = [randint(0, 101) for i in range(n)]
info()
del a
a = [i for i in range(n - 1, -1, -1)]
info()
del a
show(values)