Введение в алгоритмы сортировки

В этом небольшом примере собраны базовые понятия, структуры и примеры сортировок. Текст написан в формате 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)
   • Преимущества: простая логика
   • Недостатки: неэффективна на больших данных

Таблица сравнения

Пример кода (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)
• Изображение с визуализацией сортировок:
  

Если хотите, могу адаптировать текст под конкретный курс или тему экзамена (например, упор на временную сложность, стабильность, или сравнение конкретных алгоритмов).