Приведи пример алгоритмической сложности какого-либо алгоритма сортировки

Алгоритмическая сложность алгоритмов сортировки

Алгоритмическая сложность описывает, как растёт количество операций в зависимости от размера входных данных. Рассмотрим несколько популярных алгоритмов сортировки и их сложность.

Quick Sort (Быстрая сортировка)

Временная сложность:

• Best case: O(n log n) — когда опорный элемент делит массив на равные части
• Average case: O(n log n) — в большинстве реальных случаев
• Worst case: O(n²) — когда опорный элемент всегда минимальный или максимальный

Пространственная сложность: O(log n) — за счёт рекурсивного стека вызовов

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Merge Sort (Сортировка слиянием)

Временная сложность: O(n log n) во всех случаях

• Best, Average, Worst — всегда одинаковая

Пространственная сложность: O(n) — требует дополнительной памяти для временных массивов

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

Bubble Sort (Сортировка пузырьком)

Временная сложность:

• Best case: O(n) — если массив уже отсортирован (с оптимизацией)
• Average/Worst case: O(n²) — неэффективно для больших данных

Пространственная сложность: O(1) — сортирует на месте

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

Heap Sort (Сортировка кучей)

Временная сложность: O(n log n) во всех случаях

• Гарантирует O(n log n) даже в худшем случае

Пространственная сложность: O(1) — работает на месте

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

Сравнительная таблица

Бести, Авереж, Ворст, Память, Устойчив Bubble Sort: O(n), O(n²), O(n²), O(1), Да Quick Sort: O(n log n), O(n log n), O(n²), O(log n), Нет Merge Sort: O(n log n), O(n log n), O(n log n), O(n), Да Heap Sort: O(n log n), O(n log n), O(n log n), O(1), Нет Tim Sort: O(n), O(n log n), O(n log n), O(n), Да

Выводы

Выбирай алгоритм исходя из:

• Размера данных: для больших массивов предпочитай O(n log n)
• Стабильности: если важен порядок одинаковых элементов, используй Merge Sort или Tim Sort
• Памяти: если памяти мало, выбирай Quick Sort или Heap Sort
• На практике: Python использует Tim Sort в встроённой функции sorted(), так как он оптимален для реальных данных

Понимание алгоритмической сложности критично для написания эффективного кода и решения задач на собеседованиях.