---

import random
import time

def bubble_sort(arr):
    a = arr.copy()
    swaps = 0
    n = len(a)
    for i in range(n):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swaps += 1
    return a, swaps

def insertion_sort(arr):
    a = arr.copy()
    swaps = 0
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            swaps += 1
            j -= 1
        a[j + 1] = key
    return a, swaps

def selection_sort(arr):
    a = arr.copy()
    swaps = 0
    n = len(a)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        if min_idx != i:
            a[i], a[min_idx] = a[min_idx], a[i]
            swaps += 1
    return a, swaps

def quick_sort(arr):
    a = arr.copy()
    swaps = [0]
    def _quick(lo, hi):
        if lo < hi:
            pivot = a[hi]
            i = lo - 1
            for j in range(lo, hi):
                if a[j] <= pivot:
                    i += 1
                    if i != j:
                        a[i], a[j] = a[j], a[i]
                        swaps[0] += 1
            a[i + 1], a[hi] = a[hi], a[i + 1]
            swaps[0] += 1
            p = i + 1
            _quick(lo, p - 1)
            _quick(p + 1, hi)
    _quick(0, len(a) - 1)
    return a, swaps[0]

def merge_sort(arr):
    a = arr.copy()
    swaps = [0]
    def _merge(lo, hi):
        if hi - lo <= 1:
            return
        mid = (lo + hi) // 2
        _merge(lo, mid)
        _merge(mid, hi)
        left = a[lo:mid]
        right = a[mid:hi]
        i = j = 0
        k = lo
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                a[k] = left[i]
                i += 1
            else:
                a[k] = right[j]
                j += 1
                swaps[0] += 1
            k += 1
        while i < len(left):
            a[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            a[k] = right[j]
            j += 1
            k += 1
    _merge(0, len(a))
    return a, swaps[0]

def shaker_sort(arr):
    a = arr.copy()
    swaps = 0
    left = 0
    right = len(a) - 1
    while left < right:
        for i in range(left, right):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swaps += 1
        right -= 1
        for i in range(right, left, -1):
            if a[i - 1] > a[i]:
                a[i - 1], a[i] = a[i], a[i - 1]
                swaps += 1
        left += 1
    return a, swaps


def main():
    n = int(input("Введите размер массива: "))
    arr = [random.randint(0, 1000) for _ in range(n)]
    print("Исходный массив:", arr)

    algorithms = [
        ("Пузырьковая", bubble_sort),
        ("Вставками", insertion_sort),
        ("Выбором", selection_sort),
        ("Быстрая", quick_sort),
        ("Слиянием", merge_sort),
        ("Шейкерная", shaker_sort),
    ]

    print("\n{:<15} {:<15} {:<15}".format("Алгоритм", "Время (сек)", "Перестановки"))
    print("-" * 45)
    for name, func in algorithms:
        start = time.perf_counter()
        sorted_arr, swaps = func(arr)
        elapsed = time.perf_counter() - start
        print("{:<15} {:<15.6f} {:<15}".format(name, elapsed, swaps))

    print("\nОтсортированный массив:", sorted_arr)


if __name__ == "__main__":
    main()