---

import time
import random
from tabulate import tabulate


def bubble_sort(arr):
    """Сортировка пузырьком"""
    a = arr.copy()
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a


def merge_sort(arr):
    """Сортировка слиянием"""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def read_array_from_file(filename):
    """Чтение массива из файла (числа через пробел/запятую/с новой строки)"""
    with open(filename, 'r', encoding='utf-8') as f:
        content = f.read().replace(',', ' ').split()
        return [int(x) for x in content]


def get_input_array():
    """Получение массива от пользователя"""
    print("\nВыберите способ ввода:")
    print("1 - Ввести вручную")
    print("2 - Загрузить из файла")
    print("3 - Сгенерировать случайный массив")
    choice = input("Ваш выбор: ").strip()

    if choice == '1':
        data = input("Введите числа через пробел: ")
        return [int(x) for x in data.split()]
    elif choice == '2':
        filename = input("Имя файла: ").strip()
        return read_array_from_file(filename)
    elif choice == '3':
        n = int(input("Размер массива: "))
        return [random.randint(-1000, 1000) for _ in range(n)]
    else:
        print("Неверный выбор. Использую случайный массив из 100 элементов.")
        return [random.randint(-1000, 1000) for _ in range(100)]


def benchmark(arr, repeats=3):
    """Замер времени работы обеих сортировок"""
    # Проверка корректности
    assert bubble_sort(arr) == merge_sort(arr) == sorted(arr), "Ошибка сортировки!"

    # Bubble sort
    bubble_times = []
    for _ in range(repeats):
        start = time.perf_counter()
        bubble_sort(arr)
        bubble_times.append(time.perf_counter() - start)

    # Merge sort
    merge_times = []
    for _ in range(repeats):
        start = time.perf_counter()
        merge_sort(arr)
        merge_times.append(time.perf_counter() - start)

    return {
        'bubble_avg': sum(bubble_times) / repeats,
        'merge_avg': sum(merge_times) / repeats,
        'bubble_min': min(bubble_times),
        'merge_min': min(merge_times),
    }


def print_table(results, n):
    """Вывод результатов в виде таблицы"""
    headers = ["Алгоритм", "Среднее время (с)", "Мин. время (с)", "Сложность (сред.)", "Сложность (худш.)"]

    table = [
        ["Пузырьковая", f"{results['bubble_avg']:.6f}",
         f"{results['bubble_min']:.6f}", "O(n²)", "O(n²)"],
        ["Слиянием", f"{results['merge_avg']:.6f}",
         f"{results['merge_min']:.6f}", "O(n log n)", "O(n log n)"],
    ]

    print(f"\n{'=' * 70}")
    print(f"  Сравнение сортировок для массива из {n} элементов")
    print(f"{'=' * 70}")
    print(tabulate(table, headers=headers, tablefmt="grid"))

    # Ускорение
    if results['merge_avg'] > 0:
        speedup = results['bubble_avg'] / results['merge_avg']
        print(f"\nСортировка слиянием быстрее в {speedup:.2f} раз(а)")

    # Оценка теоретической сложности
    n2 = n * n
    nlogn = n * (n.bit_length())  # ~n log n
    print(f"\nТеоретическое соотношение (n² / n·log₂n) ≈ {n2 / nlogn:.1f}")
    print(f"Практическое соотношение (bubble / merge)    ≈ "
          f"{results['bubble_avg'] / results['merge_avg']:.1f}")


def compare_different_sizes():
    """Сравнение на массивах разного размера"""
    print("\n--- Сравнение на массивах разного размера ---")
    sizes = [100, 500, 1000, 2000, 5000]
    headers = ["Размер", "Пузырьковая (с)", "Слиянием (с)", "Отношение"]
    table = []

    for n in sizes:
        arr = [random.randint(-10000, 10000) for _ in range(n)]
        res = benchmark(arr, repeats=2)
        ratio = res['bubble_avg'] / res['merge_avg'] if res['merge_avg'] > 0 else float('inf')
        table.append([
            n,
            f"{res['bubble_avg']:.6f}",
            f"{res['merge_avg']:.6f}",
            f"{ratio:.1f}x"
        ])

    print(tabulate(table, headers=headers, tablefmt="grid"))


def main():
    print("=" * 70)
    print(" СРАВНЕНИЕ ЭФФЕКТИВНОСТИ СОРТИРОВОК: ПУЗЫРЬКОМ vs СЛИЯНИЕМ")
    print("=" * 70)

    while True:
        print("\nМеню:")
        print("1 - Сравнить на своём массиве (ручной ввод / файл / генерация)")
        print("2 - Сравнить на массивах разного размера")
        print("0 - Выход")

        choice = input("Ваш выбор: ").strip()

        if choice == '1':
            arr = get_input_array()
            print(f"\nИсходный массив ({len(arr)} элементов): {arr[:20]}"
                  f"{'...' if len(arr) > 20 else ''}")
            results = benchmark(arr)
            print_table(results, len(arr))

        elif choice == '2':
            compare_different_sizes()

        elif choice == '0':
            print("До свидания!")
            break
        else:
            print("Неверный выбор.")


if __name__ == "__main__":
    main()
pip install tabulate