🧩 Сортировка одномерного массива
Учебный материал для 11 класса

⚙️ Основные алгоритмы сортировки

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

Принцип: Последовательно проходим массив, сравнивая пары соседних элементов. Если текущий элемент больше следующего — меняем их местами. Самые большие элементы «всплывают» в конец массива, как пузырьки в газировке. Процесс повторяется, пока массив не будет упорядочен.

Сложность: O(n²) в среднем и худшем случае, O(n) — в лучшем (если массив уже отсортирован).

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]   # обмен
    return arr

🔍 2. Сортировка выбором (Selection Sort)

Принцип: Делим массив на отсортированную и неотсортированную части. На каждом шаге ищем минимальный элемент в неотсортированной части и меняем его с первым элементом этой части.

Сложность: O(n²) всегда (не зависит от исходных данных).

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

📥 3. Сортировка вставками (Insertion Sort)

Принцип: Аналогично сортировке карт в руке: левая часть массива всегда отсортирована. Берём очередной элемент и «вставляем» его в нужное место среди отсортированных, сдвигая остальные.

Сложность: O(n²) в среднем, но на почти отсортированных данных работает за O(n).

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

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

Принцип: Рекурсивный алгоритм, использующий стратегию «разделяй и властвуй». Выбирается опорный элемент (pivot), массив делится на две части: элементы меньше pivot (слева) и больше pivot (справа). Затем части сортируются рекурсивно.

Сложность: В среднем O(n log n), в худшем (неудачный выбор pivot) O(n²). На практике — один из самых быстрых.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]                     # опорный элемент
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

📊 Сравнительная таблица алгоритмов

Примечание: O-нотация показывает, как быстро растёт время выполнения при увеличении размера массива n. Например, O(n²) означает, что при увеличении n в 10 раз время возрастёт примерно в 100 раз.

🧪 Практическое задание

1. Сгенерируйте массив из 20 случайных целых чисел от 1 до 100.
2. Отсортируйте его с помощью сортировки пузырьком и быстрой сортировки.
3. Сравните время выполнения (используйте модуль time в Python). Для чистоты эксперимента запустите обе сортировки на одном и том же наборе данных.
4. Попробуйте увеличить размер массива до 1000, 10000 элементов и снова замерьте время. Сделайте выводы.

Пример замера времени на Python:

import random
import time

data = [random.randint(1,100) for _ in range(1000)]

# Копируем массив, чтобы не повлиять на второй алгоритм
arr1 = data.copy()
start = time.time()
bubble_sort(arr1)
end = time.time()
print("Bubble sort time:", end - start)

arr2 = data.copy()
start = time.time()
sorted_arr = quick_sort(arr2)
end = time.time()
print("Quick sort time:", end - start)

🏠 Домашнее задание

• Выучить основные алгоритмы сортировки (названия, идеи, временную сложность).
• Реализовать сортировку вставками на любом языке программирования (Python, Pascal, C++).
• Подготовить краткое сообщение о том, какой алгоритм сортировки используется во встроенной функции sorted() в Python (Timsort) и в чём его преимущество.
• (Для продвинутых) Реализовать сортировку слиянием (Merge Sort) и сравнить её производительность с быстрой сортировкой.