Какие алгоритмы сортировки вы знаете?

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

• Сортировка пузырьком (Bubble Sort): Простой, но неэффективный алгоритм, многократно проходящий по списку, меняя местами соседние элементы, если они в неправильном порядке.
• Сортировка выбором (Selection Sort): Находит наименьший (или наибольший) элемент из неотсортированной части списка и помещает его в начало.
• Сортировка вставками (Insertion Sort): Постепенно строит отсортированный список, вставляя каждый новый элемент в нужное место уже отсортированной части.
• Сортировка слиянием (Merge Sort): Рекурсивный алгоритм, разбивающий список на подсписки, сортирующий их и затем объединяющий обратно.
• Быстрая сортировка (Quick Sort): Алгоритм "разделяй и властвуй", выбирающий опорный элемент (pivot) и перераспределяющий элементы так, чтобы элементы меньше опорного оказались слева, а больше - справа. Затем рекурсивно применяется к подспискам.
• Сортировка Шелла (Shell Sort): Улучшение сортировки вставками, использующее сравнения на больших расстояниях между элементами.
• Пирамидальная сортировка (Heap Sort): Использует структуру данных "куча" (heap) для эффективной сортировки.

Также существуют менее распространенные, но эффективные в определенных случаях алгоритмы, такие как сортировка подсчетом (Counting Sort), поразрядная сортировка (Radix Sort), блочная сортировка (Bucket Sort).

Время выполнения основных алгоритмов (в среднем):

Пример реализации быстрой сортировки на Python:

def quicksort(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 quicksort(left) + middle + quicksort(right) # Рекурсивная сортировка и объединение