# Введение в алгоритмы сортировки В этом небольшом примере собраны базовые понятия, структуры и примеры сортировок. Текст написан в формате Markdown, чтобы удобно использовать на лекциях и в заметках. ## Основные понятия - Алгоритм сортировки преобразует произвольный массив данных в упорядоченный - Время работы часто оценивают по наихудшему случаю: O(n^2), O(n log n) и т. д. - Важные характеристики: - стабильность: сохраняется ли относительный порядок равных элементов? - потребление памяти: in-place или требуют дополнительной памяти - размер входа и особенности данных ## Основные алгоритмы 1. Сортировка пузырьком (Bubble sort) - Сложность: O(n^2) - Преимущества: простота реализации - Недостатки: медленная на больших наборах данных 2. Сортировка вставками (Insertion sort) - Сложность: O(n^2) - Преимущества: хорошо работает на почти отсортированных данных - Недостатки: всё ещё медленно на больших наборах 3. Быстрая сортировка (Quicksort) - Сложность: в среднем O(n log n), в худшем O(n^2) - Преимущества: очень быстрая в среднем - Недостатки: зависит от выбора опорного элемента 4. Сортировка слиянием (Merge sort) - Сложность: O(n log n) - Преимущества: стабильна, подходит для внешней памяти - Недостатки: требует дополнительной памяти 5. Пирамидальная сортировка (Heap sort) - Сложность: O(n log n) - Преимущества: не требует дополнительной памяти - Недостатки: может быть менее быстрой по константам по сравнению с QuickSort 6. Сортировка выбором (Selection sort) - Сложность: O(n^2) - Преимущества: простая логика - Недостатки: неэффективна на больших данных ## Таблица сравнения | Алгоритм | Время (среднее) | Стабильность | Применение | |--------------------|------------------|--------------|-------------------------------------------| | Bubble sort | O(n^2) | Нет | маленькие наборы, обучающие примеры | | Insertion sort | O(n^2) | Да | почти отсортированные входы | | Quick sort | O(n log n) | Нет | общие задачи, средние данные | | Merge sort | O(n log n) | Да | внешняя память, требовательная к стабильности | | Heap sort | O(n log n) | Нет | ограничения памяти | | Selection sort | O(n^2) | Нет | базовая иллюстрация концепций | ## Пример кода (Python) ```python # Простая реализация сортировки пузырьком def bubble_sort(arr): a = arr[:] 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 # Пример использования if __name__ == "__main__": data = [64, 34, 25, 12, 22, 11, 90] print("Исходный:", data) print("Отсортированный пузырьком:", bubble_sort(data)) ``` ## Блокнот-навык > Примечание: выбор конкретного алгоритма зависит от контекста задачи: > размер данных, распределение значений, требования к стабильности и памяти. ## Дополнительные материалы - [Документация по Python (sorted и list.sort)](https://docs.python.org/3/howto/sorting.html) - Изображение с визуализацией сортировок:  Если хотите, могу адаптировать текст под конкретный курс или тему экзамена (например, упор на временную сложность, стабильность, или сравнение конкретных алгоритмов).