Практическая работа 1 пара

Практическое занятие №1 «Оценка сложности алгоритмов сортировки»

Практическая работа по асимптотической оценке и экспериментальному сравнению алгоритмов сортировки.

Цель работы

На практике сравнить алгоритмы сортировки не по субъективному ощущению «быстро/медленно», а по количеству выполняемых операций и скорости роста затрат при увеличении размера массива.

Главная идея: нас интересует не точное число миллисекунд на одном компьютере, а то, как быстро растёт объём работы при росте n.

Что нужно знать перед началом

Обозначение	Смысл
`O(1)`	Количество работы почти не зависит от размера входных данных.
`O(n)`	При увеличении `n` примерно в 2 раза объём работы растёт примерно в 2 раза.
`O(n log n)`	Растёт быстрее линейного, но значительно медленнее квадратичного.
`O(n²)`	При увеличении `n` в 2 раза объём работы может вырасти примерно в 4 раза.

Исходный код

Создайте файл sorting_complexity.py и вставьте код:

from random import randint
from timeit import repeat


def bubble_sort(data):
    a = data.copy()
    comparisons = 0

    for i in range(len(a) - 1):
        swapped = False

        for j in range(len(a) - 1 - i):
            comparisons += 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, comparisons


def insertion_sort(data):
    a = data.copy()
    comparisons = 0

    for i in range(1, len(a)):
        key = a[i]
        j = i - 1

        while j >= 0:
            comparisons += 1

            if a[j] > key:
                a[j + 1] = a[j]
                j -= 1
            else:
                break

        a[j + 1] = key

    return a, comparisons


def merge_sort(data):
    comparisons = 0

    def sort(a):
        nonlocal comparisons

        if len(a) <= 1:
            return a

        mid = len(a) // 2
        left = sort(a[:mid])
        right = sort(a[mid:])

        result = []
        i = j = 0

        while i < len(left) and j < len(right):
            comparisons += 1

            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

    return sort(data.copy()), comparisons


def measure(func, data):
    times = repeat(lambda: func(data), repeat=5, number=1)
    return min(times)


algorithms = {
    "Пузырьковая": bubble_sort,
    "Вставками": insertion_sort,
    "Слиянием": merge_sort,
}

sizes = [100, 500, 1000]

for n in sizes:
    random_data = [randint(0, 100000) for _ in range(n)]

    print(f"\nРазмер массива: {n}")

    for name, func in algorithms.items():
        _, comparisons = func(random_data)
        t = measure(func, random_data)

        print(
            f"{name:12} | "
            f"сравнений: {comparisons:8} | "
            f"время: {t:.6f} с"
        )

Ход работы

Запустите программу без изменений и убедитесь, что все три алгоритма работают.
Заполните таблицу для случайных массивов размером 100, 500 и 1000 элементов.
Для n = 1000 отдельно проверьте три вида входных данных:
- уже отсортированный массив: list(range(n));
- массив в обратном порядке: list(range(n, 0, -1));
- случайный массив.
Сравните, как меняется число сравнений у пузырьковой сортировки и сортировки вставками в зависимости от исходного порядка.
Сравните рост затрат при переходе от 100 к 1000 элементам. Определите класс сложности каждого алгоритма.

Алгоритм	n	Тип входных данных	Сравнений	Время, с
	100	случайные
	500	случайные
	1000	случайные
	1000	отсортированные
	1000	обратный порядок

Задания для анализа

Почему два алгоритма с классом O(n²) могут показывать разное время на одинаковом массиве?
Как изменится объём работы алгоритма O(n²), если размер массива увеличить примерно в 10 раз?
Почему сортировка вставками работает особенно хорошо на почти отсортированных данных?
Почему измерение времени само по себе не является доказательством класса сложности?
Какой из трёх алгоритмов лучше масштабируется при больших n? Обоснуйте через характер роста, а не одной цифрой времени.

Что показать преподавателю

Запускающийся файл с тремя алгоритмами.
Заполненную таблицу измерений.
Классы сложности: лучший/типичный/худший случай там, где они различаются.
Краткий вывод на 4–6 предложений.

Ориентир по времени

10 минут — разбор задания; 45–50 минут — код и измерения; 15 минут — анализ таблиц; 5 минут — вывод. Если пара длится 90 минут, оставшееся время используйте для дополнительного задания.

Дополнительное задание

Добавьте sorted(data) и сравните встроенную сортировку Python с учебными реализациями. Не пытайтесь определять её сложность только по одному замеру: сформулируйте лишь экспериментальный вывод.