9 laba

# ---------------------------------
# МЕТОДЫ СОРТИРОВКИ
# ВЫПОЛНИЛ: ДМИТРИЙ МИШУТИН, КЭ - 101
# ---------------------------------

import random
import time
import copy


def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


def quick_sort(arr, l, r):
    i = l
    j = r
    x = arr[(l + r) // 2]
    while i <= j:
        while arr[i] < x:
            i += 1
        while x < arr[j]:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    if l < j:
        quick_sort(arr, l, j)
    if i < r:
        quick_sort(arr, i, r)


def insertion_sort(arr):
    for i in range(len(arr)):
        compare = arr[i]
        j = i
        while arr[j - 1] > compare and j > 0:
            arr[j] = arr[j - 1]
            j = j - 1
        arr[j] = compare


print("Вариант", (24 + 5 + 1999) % 4 + 1)
n = int(input("Введите n: "))

norm_bubble = [i for i in range(1, n + 1)]
norm_quick = [i for i in range(1, n + 1)]
norm_insert = [i for i in range(1, n + 1)]

rand_bubble = [random.randint(-100, 100) for i in range(n)]
rand_quick = copy.deepcopy(rand_bubble)
rand_insert = copy.deepcopy(rand_bubble)

rev_bubble = [i for i in range(n, 0, -1)]
rev_quick = [i for i in range(n, 0, -1)]
rev_insert = [i for i in range(n, 0, -1)]

start = time.clock()
bubble_sort(norm_bubble)
time_bubble_norm = time.clock() - start

start = time.clock()
bubble_sort(rand_bubble)
time_bubble_rand = time.clock() - start

start = time.clock()
bubble_sort(rev_bubble)
time_bubble_rev = time.clock() - start

start = time.clock()
quick_sort(norm_quick, 0, n - 1)
time_quick_norm = time.clock() - start

start = time.clock()
quick_sort(rand_quick, 0, n - 1)
time_quick_rand = time.clock() - start

start = time.clock()
quick_sort(rev_quick, 0, n - 1)
time_quick_rev = time.clock() - start

start = time.clock()
insertion_sort(norm_insert)
time_insert_norm = time.clock() - start

start = time.clock()
insertion_sort(rand_insert)
time_insert_rand = time.clock() - start

start = time.clock()
insertion_sort(rev_insert)
time_insert_rev = time.clock() - start

print("Метод\tОтсортированная\t\tСлучайная\t\tВ обратном порядке")
print("Пузырёк\t", time_bubble_norm, "\t", time_bubble_rand, "\t", time_bubble_rev, sep = "")
print("Быстрая\t", time_quick_norm, "\t", time_quick_rand, "\t", time_quick_rev, sep = "")
print("Вставки\t", time_insert_norm, "\t", time_insert_rand, "\t", time_insert_rev, sep = "")