import random, time

def main():
    global time_bubble, time_choice, time_quick
    time_bubble = []
    time_choice = []
    time_quick = []
    print("Вариант: ", 2025 % 4 + 1)
    N = int(input("Кол-во элементов: "))

    random_array = []
    array_sort = [x for x in range(1, N)]
    array_reverse_sort = [x for x in range(N, 1, -1)]

    for i in range(1, N):
        random_array.append(random.randint(1, 1000))

    bubble_sort(array_sort)
    bubble_sort(random_array)
    bubble_sort(array_reverse_sort)
    choice_sort(array_sort)
    choice_sort(random_array)
    choice_sort(array_reverse_sort)
    time_for_quick(array_sort, random_array, array_reverse_sort)

    print('{0:10} | {1:15} | {2:9} | {3:40}'.format("Метод", "отсортированная", "случайная", "отсортированная в обратном порядке"))
    print('{0:10} | {1:15f} | {2:9f} | {3:34f}'.format("Bubble", time_bubble[0], time_bubble[2], time_bubble[4]), time_bubble[1], time_bubble[3], time_bubble[5])
    print('{0:10} | {1:15f} | {2:9f} | {3:34f}'.format("Choice", time_choice[0], time_choice[2], time_choice[4]), time_choice[1], time_choice[3], time_choice[5])
    print('{0:10} | {1:15f} | {2:9f} | {3:34f}'.format("Quick", time_quick[0], time_quick[2], time_quick[4]), time_quick[1]) #допиши это говно


def check(arr):
    n = len(arr) - 1
    for i in range(0, n):
        if arr[i] > arr[i+1]:
            return False
    return True


def quick_sort(arr, start, end):
    l = start
    r = end
    t = (l + r) // 2
    while l != r:
        while l < t and arr[l] <= arr[t]:
            l += 1
        arr[l], arr[t] = arr[t], arr[l]
        t = l
        while r > t and arr[r] >= arr[t]:
            r -= 1
        arr[r], arr[t] = arr[t], arr[r]
        t = r
    if t - 1 > start:
        quick_sort(arr, start, t - 1)
    if t + 1 < end:
        quick_sort(arr, t + 1, end)


def choice_sort(arr):
    n = len(arr)
    arr1 = arr.copy()
    i = 0
    time_start = time.time()

    while i < n - 1:
        small = i
        j = i + 1
        while j < n:
            if arr1[j] < arr1[small]:
                small = j
            j += 1
        arr1[i], arr1[small] = arr1[small], arr1[i]
        i += 1

    time_end = time.time()
    time_choice.append(time_end - time_start)
    time_choice.append(check(arr1))


def bubble_sort(arr):
    arr1 = arr.copy()
    time_start = time.time()
    n = 1
    while n < len(arr1):
        for i in range(len(arr1) - n):
            if arr1[i] > arr1[i + 1]:
                arr1[i], arr1[i + 1] = arr1[i + 1], arr1[i]
        n += 1
    time_end = time.time()
    time_bubble.append(time_end - time_start)
    time_bubble.append(check(arr1))

def time_for_quick(a, b, c):
    time_start = time.time()
    quick_sort(a, 0, len(a) - 1)
    time_end = time.time()
    time_quick.append(time_end - time_start)
    time_quick.append(check(a))
    time_start = time.time()
    quick_sort(a, 0, len(b) - 1)
    time_end = time.time()
    time_quick.append(time_end - time_start)
    time_start = time.time()
    quick_sort(a, 0, len(c) - 1)
    time_end = time.time()
    time_quick.append(time_end - time_start)

if __name__ == '__main__':
    main()