Sorting algorithm

Определение

Алгоритмы сортировки — это наборы инструкций, которые принимают на вход неупорядоченный список элементов и возвращают его в определённом порядке (по возрастанию или убыванию).

Подходы к реализации

Все алгоритмы сортировки можно разделить на две большие группы по принципу их работы:

• Итеративные (Простые): используют вложенные циклы для постепенного перемещения элементов на свои места. Подходят для небольших данных.
  Примеры: Bubble Sort Selection Sort Insertion Sort.

• Рекурсивные (Сложные): основаны на стратегии «Разделяй и властвуй» (Divide and Conquer). Они разбивают массив на части, сортируют их и соединяют обратно.
  Примеры: Merge Sort Quick Sort.

Характеристики алгоритмов

При выборе алгоритма разработчики ориентируются на три ключевых показателя.

Алгоритм	Среднее время	Память	Стабильный?	Особенности
Bubble Sort	O(n²)	O(1)	Да	Много лишних обменов
Selection Sort	O(n²)	O(1)	Нет	Минимум операций записи
Quick Sort	O(nlogn)	O(logn)	Нет	Самый быстрый на практике
Merge Sort	O(nlogn)	O(n)	Да	Гарантированная скорость

Популярные алгоритмы

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

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

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

Алгоритм выбирает опорный элемент (pivot) и распределяет остальные элементы в две группы: те, что меньше опорного, и те, что больше. Затем процесс рекурсивно повторяется для каждой группы.

    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)

Ключевые мысли

• Встроенная сортировка в Python (.sort() и sorted()) использует алгоритм Timsort, который объединяет лучшие черты сортировки вставками и слиянием.

• Для маленьких списков часто лучше использовать простые алгоритмы, так как у них меньше накладных расходов на вызовы функций.

• Память — критический фактор: если её мало, выбирайте Quick Sort или Heap Sort, а не Merge Sort.