Алгоритмы сортировки — это фундаментальная часть программирования, которая встречается на каждом техническом собеседовании. Понимание различных алгоритмов сортировки, их временной и пространственной сложности поможет вам выбрать оптимальное решение для конкретной задачи.

Зачем изучать алгоритмы сортировки?

Знание алгоритмов сортировки важно по нескольким причинам:

• Технические собеседования — сортировка часто является основой для более сложных задач
• Понимание сложности — помогает анализировать эффективность алгоритмов
• Практическое применение — многие задачи требуют предварительной сортировки данных
• Фундаментальные знания — основа для изучения более продвинутых алгоритмов

Классификация алгоритмов сортировки

1. Пузырьковая сортировка (Bubble Sort)

Простейший алгоритм сортировки, который сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке.

def bubble_sort(arr):
    """
    Пузырьковая сортировка
    
    Временная сложность: O(n²)
    Пространственная сложность: O(1)
    Стабильность: Да
    """
    n = len(arr)
    
    for i in range(n):
        # Флаг для оптимизации - если за проход не было перестановок, массив отсортирован
        swapped = False
        
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # Если не было перестановок, массив уже отсортирован
        if not swapped:
            break
    
    return arr

# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print("Исходный массив:", numbers)
bubble_sort(numbers)
print("Отсортированный массив:", numbers)

Применение: Образовательные цели, маленькие массивы данных.

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

Алгоритм находит минимальный элемент и ставит его в начало, затем повторяет процесс для остальной части массива.

def selection_sort(arr):
    """
    Сортировка выбором
    
    Временная сложность: O(n²)
    Пространственная сложность: O(1)
    Стабильность: Нет
    """
    n = len(arr)
    
    for i in range(n):
        # Находим индекс минимального элемента в оставшейся части
        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

# Пример использования
numbers = [64, 25, 12, 22, 11]
print("Selection Sort:", selection_sort(numbers.copy()))

Применение: Когда важно минимизировать количество записей в память.

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

Строит отсортированную последовательность по одному элементу за раз, вставляя каждый новый элемент в правильную позицию.

def insertion_sort(arr):
    """
    Сортировка вставками
    
    Временная сложность: O(n²) худший случай, O(n) лучший случай
    Пространственная сложность: O(1)
    Стабильность: Да
    Адаптивность: Да
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Сдвигаем элементы arr[0..i-1], которые больше key,
        # на одну позицию вперед
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

# Пример использования
numbers = [12, 11, 13, 5, 6]
print("Insertion Sort:", insertion_sort(numbers.copy()))

Применение: Небольшие массивы, частично отсортированные данные, онлайн-алгоритмы.

4. Сортировка слиянием (Merge Sort)

Алгоритм "разделяй и властвуй", который рекурсивно делит массив пополам и затем сливает отсортированные части.

def merge_sort(arr):
    """
    Сортировка слиянием
    
    Временная сложность: O(n log n) всегда
    Пространственная сложность: O(n)
    Стабильность: Да
    """
    if len(arr) <= 1:
        return arr
    
    # Делим массив пополам
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # Сливаем отсортированные части
    return merge(left, right)

def merge(left, right):
    """Слияние двух отсортированных массивов"""
    result = []
    i, j = 0, 0
    
    # Сравниваем элементы из обеих частей
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Добавляем оставшиеся элементы
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# Пример использования
numbers = [38, 27, 43, 3, 9, 82, 10]
print("Merge Sort:", merge_sort(numbers))

Применение: Большие массивы, когда нужна стабильная сортировка, внешняя сортировка.

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

Эффективный алгоритм "разделяй и властвуй", использующий элемент-разделитель (pivot) для разбиения массива.

def quick_sort(arr, low=0, high=None):
    """
    Быстрая сортировка
    
    Временная сложность: O(n log n) средний случай, O(n²) худший случай
    Пространственная сложность: O(log n) средний случай
    Стабильность: Нет
    """
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # pi - индекс разделения, arr[pi] теперь на правильном месте
        pi = partition(arr, low, high)
        
        # Рекурсивно сортируем элементы до и после разделения
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
    
    return arr

def partition(arr, low, high):
    """Разделение массива относительно pivot"""
    # Выбираем последний элемент как pivot
    pivot = arr[high]
    
    i = low - 1  # Индекс меньшего элемента
    
    for j in range(low, high):
        # Если текущий элемент меньше или равен pivot
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Пример использования
numbers = [10, 7, 8, 9, 1, 5]
print("Quick Sort:", quick_sort(numbers.copy()))

Применение: Общего назначения, когда важна скорость и не критична стабильность.

6. Пирамидальная сортировка (Heap Sort)

Использует структуру данных "куча" для эффективной сортировки.

def heap_sort(arr):
    """
    Пирамидальная сортировка
    
    Временная сложность: O(n log n) всегда
    Пространственная сложность: O(1)
    Стабильность: Нет
    """
    n = len(arr)
    
    # Строим max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Извлекаем элементы из кучи один за другим
    for i in range(n - 1, 0, -1):
        # Перемещаем текущий корень в конец
        arr[0], arr[i] = arr[i], arr[0]
        
        # Вызываем heapify для уменьшенной кучи
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    """Поддержание свойства кучи"""
    largest = i  # Инициализируем наибольший как корень
    left = 2 * i + 1     # левый дочерний элемент
    right = 2 * i + 2    # правый дочерний элемент
    
    # Если левый дочерний больше корня
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # Если правый дочерний больше наибольшего на данный момент
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # Если наибольший не корень
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        
        # Рекурсивно heapify затронутое поддерево
        heapify(arr, n, largest)

# Пример использования
numbers = [12, 11, 13, 5, 6, 7]
print("Heap Sort:", heap_sort(numbers.copy()))

Применение: Когда нужна гарантированная производительность O(n log n).

7. Сортировка подсчетом (Counting Sort)

Неcравнительный алгоритм, эффективный для сортировки целых чисел в ограниченном диапазоне.

def counting_sort(arr):
    """
    Сортировка подсчетом
    
    Временная сложность: O(n + k), где k - диапазон входных данных
    Пространственная сложность: O(k)
    Стабильность: Да
    """
    if not arr:
        return arr
    
    # Находим максимальное и минимальное значения
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1
    
    # Создаем массив для подсчета
    count = [0] * range_val
    output = [0] * len(arr)
    
    # Подсчитываем вхождения каждого элемента
    for num in arr:
        count[num - min_val] += 1
    
    # Преобразуем count[i] так, чтобы он содержал фактическое
    # положение элемента в output[]
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # Строим выходной массив
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1
    
    return output

# Пример использования
numbers = [4, 2, 2, 8, 3, 3, 1]
print("Counting Sort:", counting_sort(numbers))

Применение: Сортировка целых чисел в ограниченном диапазоне.

8. Поразрядная сортировка (Radix Sort)

Сортирует числа поразрядно, начиная с младшего разряда.

def radix_sort(arr):
    """
    Поразрядная сортировка
    
    Временная сложность: O(d * (n + k)), где d - количество разрядов
    Пространственная сложность: O(n + k)
    Стабильность: Да
    """
    if not arr:
        return arr
    
    # Находим максимальное число для определения количества разрядов
    max_num = max(arr)
    
    # Выполняем counting sort для каждого разряда
    exp = 1
    while max_num // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10
    
    return arr

def counting_sort_for_radix(arr, exp):
    """Counting sort для определенного разряда"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # Подсчитываем вхождения каждой цифры
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    
    # Преобразуем count[i] для получения фактических позиций
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Строим выходной массив
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    
    # Копируем выходной массив в arr[]
    for i in range(len(arr)):
        arr[i] = output[i]

# Пример использования
numbers = [170, 45, 75, 90, 2, 802, 24, 66]
print("Radix Sort:", radix_sort(numbers.copy()))

Применение: Сортировка больших массивов целых чисел или строк фиксированной длины.

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

Встроенные функции сортировки в Python

Python предоставляет эффективные встроенные функции для сортировки:

# Встроенная функция sorted() - создает новый отсортированный список
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = sorted(numbers)
print("Sorted():", sorted_numbers)
print("Исходный массив:", numbers)  # Не изменился

# Метод list.sort() - сортирует список на месте
numbers = [64, 34, 25, 12, 22, 11, 90]
numbers.sort()
print("List.sort():", numbers)  # Исходный список изменился

# Сортировка в обратном порядке
numbers = [64, 34, 25, 12, 22, 11, 90]
numbers.sort(reverse=True)
print("Reverse:", numbers)

# Сортировка с пользовательской функцией
students = [('Alice', 85), ('Bob', 90), ('Charlie', 78)]
students.sort(key=lambda x: x[1])  # Сортировка по оценкам
print("По оценкам:", students)

# Сортировка строк по длине
words = ['python', 'java', 'c', 'javascript']
words.sort(key=len)
print("По длине:", words)

Практические советы

Когда использовать какой алгоритм?

def choose_sorting_algorithm(data_size, data_type, stability_required, memory_limited):
    """
    Помощник выбора алгоритма сортировки
    """
    if data_size < 10:
        return "Insertion Sort - простой и эффективный для маленьких массивов"
    
    if data_type == "integers" and max(data) - min(data) < data_size:
        return "Counting Sort - линейная сложность для ограниченного диапазона"
    
    if stability_required and not memory_limited:
        return "Merge Sort - стабильная и предсказуемая O(n log n)"
    
    if not stability_required and not memory_limited:
        return "Quick Sort - в среднем самая быстрая"
    
    if memory_limited:
        return "Heap Sort - гарантированная O(n log n) и O(1) память"
    
    return "Python встроенная sort() - оптимизированная Timsort"

# Примеры использования
print(choose_sorting_algorithm(5, "mixed", False, False))
print(choose_sorting_algorithm(1000, "integers", True, False))
print(choose_sorting_algorithm(10000, "mixed", False, True))

Тестирование производительности

import time
import random

def benchmark_sort_algorithms(size=1000):
    """Сравнение производительности алгоритмов сортировки"""
    
    # Генерируем случайные данные
    data = [random.randint(1, 1000) for _ in range(size)]
    
    algorithms = {
        'Bubble Sort': bubble_sort,
        'Selection Sort': selection_sort,
        'Insertion Sort': insertion_sort,
        'Merge Sort': merge_sort,
        'Quick Sort': lambda arr: quick_sort(arr.copy()),
        'Heap Sort': heap_sort,
        'Python sorted()': sorted
    }
    
    results = {}
    
    for name, func in algorithms.items():
        data_copy = data.copy()
        start_time = time.time()
        
        try:
            func(data_copy)
            end_time = time.time()
            results[name] = end_time - start_time
        except:
            results[name] = "Error"
    
    return results

# Запуск бенчмарка
print("Время выполнения для 1000 элементов:")
for algorithm, time_taken in benchmark_sort_algorithms().items():
    if isinstance(time_taken, float):
        print(f"{algorithm}: {time_taken:.6f} секунд")
    else:
        print(f"{algorithm}: {time_taken}")

Частые ошибки при реализации

1. Неправильная обработка границ

undefined

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Неправильно - выход за границы массива

def wrong_bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr)): # Ошибка: j может быть равно len(arr)-1 if arr[j] > arr[j + 1]: # IndexError! arr[j], arr[j + 1] = arr[j + 1], arr[j]

Правильно

def correct_bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr) - 1 - i): # Правильные границы if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]

### 2. Забыть про базовый случай в рекурсии

```python
# Неправильно - отсутствует базовый случай
def wrong_merge_sort(arr):
    mid = len(arr) // 2
    left = wrong_merge_sort(arr[:mid])   # Бесконечная рекурсия!
    right = wrong_merge_sort(arr[mid:])
    return merge(left, right)

# Правильно
def correct_merge_sort(arr):
    if len(arr) <= 1:  # Базовый случай
        return arr
    mid = len(arr) // 2
    left = correct_merge_sort(arr[:mid])
    right = correct_merge_sort(arr[mid:])
    return merge(left, right)

Заключение

Алгоритмы сортировки — это основа компьютерных наук и важный инструмент каждого программиста. Понимание различных подходов, их сильных и слабых сторон поможет вам:

• Эффективно решать задачи — выбирать оптимальный алгоритм для конкретной ситуации
• Проходить собеседования — демонстрировать глубокие знания алгоритмов
• Писать качественный код — понимать компромиссы между временем и памятью

Практикуйтесь в реализации различных алгоритмов, анализируйте их сложность и применяйте в реальных проектах. Это сделает вас более сильным разработчиком!

Дополнительные ресурсы

• Visualgo - Визуализация алгоритмов сортировки
• LeetCode - Задачи на сортировку
• Python документация - Sorting HOW TO
• Алгоритмы сортировки на CodeForces