Виды сортировки на Python
Введение
Сортировка — процесс упорядочивания элементов в определённой последовательности (по возрастанию или убыванию). Это одна из фундаментальных задач в программировании, имеющая множество практических применений: от отображения данных пользователю до оптимизации алгоритмов поиска.
1. Встроенные методы сортировки в Python
1.1. Метод sort() для списков
Принцип работы: Встроенный метод списка, использующий алгоритм Timsort — гибридный алгоритм, сочетающий сортировку слиянием и сортировку вставками. Алгоритм адаптируется к данным: для почти отсортированных массивов работает быстрее.
Сложность:
- Средний случай: O(n log n)
- Лучший случай: O(n) (уже отсортированный массив)
- Худший случай: O(n log n)
- Память: O(n)
# Пример использования sort()
numbers = [64, 34, 25, 12, 22, 11, 90]
numbers.sort()
print(f"Отсортированный список: {numbers}")
# Вывод: [11, 12, 22, 25, 34, 64, 90]
# Сортировка по ключу (например, по длине строки)
words = ["яблоко", "апельсин", "банан", "киви"]
words.sort(key=len)
print(f"Слова, отсортированные по длине: {words}")
# Вывод: ['киви', 'банан', 'яблоко', 'апельсин']
1.2. Функция sorted()
Принцип работы: Так же использует алгоритм Timsort, но создаёт новый отсортированный список, не изменяя исходный. Работает с любыми итерируемыми объектами.
Сложность: Аналогично sort(): O(n log n) в среднем случае, O(n) в лучшем.
# Пример использования sorted()
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = sorted(numbers)
print(f"Исходный список: {numbers}")
print(f"Отсортированный список: {sorted_numbers}")
# Сортировка кортежа
tuple_data = (5, 2, 8, 1, 9)
sorted_tuple = sorted(tuple_data)
print(f"Отсортированный кортеж (как список): {sorted_tuple}")
2. Алгоритмы сортировки
2.1. Сортировка пузырьком (Bubble Sort)
Принцип работы: Алгоритм проходит по списку, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Этот процесс повторяется до тех пор, пока список не будет отсортирован. Название происходит от того, что более крупные элементы "всплывают" к концу списка, подобно пузырькам в воде.
Сложность:
- Лучший случай: O(n) (уже отсортированный массив)
- Средний случай: O(n²)
- Худший случай: O(n²) (массив в обратном порядке)
- Память: O(1) (in-place)
def bubble_sort(arr):
"""
Сортировка пузырьком.
Принцип: многократный проход по массиву с обменом соседних элементов.
"""
n = len(arr)
# Проходим по списку n-1 раз
for i in range(n-1):
swapped = False # Флаг оптимизации для уже отсортированного массива
# Последние i элементов уже на своих местах
for j in range(n-1-i):
# Если текущий элемент больше следующего, меняем их местами
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(f"Сортировка пузырьком: {bubble_sort(numbers.copy())}")
2.2. Сортировка выбором (Selection Sort)
Принцип работы: Алгоритм делит список на две части: отсортированную (в начале) и неотсортированную (остальную). На каждом шаге находится минимальный элемент из неотсортированной части и перемещается в конец отсортированной. Таким образом, отсортированная часть постепенно увеличивается.
Сложность:
- Все случаи: O(n²) (даже для уже отсортированного массива)
- Память: O(1) (in-place)
def selection_sort(arr):
"""
Сортировка выбором.
Принцип: поиск минимального элемента в неотсортированной части
и перемещение его в отсортированную часть.
"""
n = len(arr)
for i in range(n):
# Предполагаем, что минимальный элемент находится на позиции i
min_index = i
# Ищем минимальный элемент в оставшейся части списка
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# Меняем местами найденный минимальный элемент с элементом на позиции i
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"Сортировка выбором: {selection_sort(numbers.copy())}")
2.3. Сортировка вставками (Insertion Sort)
Принцип работы: Алгоритм строит отсортированную последовательность постепенно, вставляя каждый новый элемент в правильную позицию относительно уже отсортированных элементов. Работает аналогично тому, как люди сортируют карты в руке.
Сложность:
- Лучший случай: O(n) (уже отсортированный массив)
- Средний случай: O(n²)
- Худший случай: O(n²) (массив в обратном порядке)
- Память: O(1) (in-place)
def insertion_sort(arr):
"""
Сортировка вставками.
Принцип: построение отсортированной последовательности
путем вставки элементов в правильную позицию.
"""
n = len(arr)
for i in range(1, n):
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
# Вставляем key в правильную позицию
arr[j + 1] = key
return arr
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"Сортировка вставками: {insertion_sort(numbers.copy())}")
2.4. Быстрая сортировка (Quick Sort)
Принцип работы: Алгоритм использует стратегию "разделяй и властвуй". Выбирается опорный элемент (pivot), массив разделяется на две части: элементы меньше опорного и элементы больше опорного. Затем рекурсивно сортируются обе части. Эффективность зависит от выбора опорного элемента.
Сложность:
- Лучший случай: O(n log n) (сбалансированное разбиение)
- Средний случай: O(n log n)
- Худший случай: O(n²) (несбалансированное разбиение)
- Память: O(log n) для рекурсии в среднем случае, O(n) в худшем
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)
def quick_sort_in_place(arr, low=0, high=None):
"""
Быстрая сортировка на месте (in-place).
Более эффективна по памяти.
"""
if high is None:
high = len(arr) - 1
if low < high:
# Разделение массива и получение индекса опорного элемента
pivot_index = partition(arr, low, high)
# Рекурсивная сортировка левой и правой частей
quick_sort_in_place(arr, low, pivot_index - 1)
quick_sort_in_place(arr, pivot_index + 1, high)
return arr
def partition(arr, low, high):
"""
Вспомогательная функция для быстрой сортировки на месте.
"""
# Выбираем опорный элемент (последний элемент)
pivot = arr[high]
i = low - 1 # Индекс меньшего элемента
for j in range(low, high):
# Если текущий элемент меньше или равен опорному
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 = [64, 34, 25, 12, 22, 11, 90, 25]
print(f"Быстрая сортировка: {quick_sort(numbers.copy())}")
print(f"Быстрая сортировка на месте: {quick_sort_in_place(numbers.copy())}")
2.5. Сортировка слиянием (Merge Sort)
Принцип работы: Алгоритм "разделяй и властвуй", который рекурсивно делит массив пополам до тех пор, пока не останутся подмассивы из одного элемента, затем объединяет их в отсортированном порядке. Стабильная сортировка, которая гарантирует сложность O(n log n) в любом случае.
Сложность:
- Все случаи: O(n log n)
- Память: O(n) (требуется дополнительный массив)
def merge_sort(arr):
"""
Сортировка слиянием.
Принцип: разделяй и властвуй с последующим слиянием отсортированных частей.
"""
if len(arr) <= 1:
return arr
# Делим список на две половины
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Рекурсивно сортируем каждую половину
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
# Объединяем отсортированные половины
return merge(left_half, right_half)
def merge(left, right):
"""
Вспомогательная функция для слияния двух отсортированных списков.
Принцип: сравнение первых элементов каждого списка и выбор меньшего.
"""
result = []
i = j = 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 = [64, 34, 25, 12, 22, 11, 90]
print(f"Сортировка слиянием: {merge_sort(numbers.copy())}")
2.6. Пирамидальная сортировка (Heap Sort)
Принцип работы: Алгоритм использует структуру данных "куча" (бинарная куча). Сначала строится max-heap (куча, где каждый родитель больше своих потомков), затем максимальный элемент (корень) перемещается в конец массива, и куча перестраивается без этого элемента. Процесс повторяется до полной сортировки.
Сложность:
- Все случаи: O(n log n)
- Память: O(1) (in-place)
def heap_sort(arr):
"""
Пирамидальная сортировка.
Принцип: использование структуры данных "куча" для сортировки.
"""
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(arr, i, 0) # Вызываем heapify на уменьшенной куче
return arr
def heapify(arr, n, i):
"""
Вспомогательная функция для преобразования поддерева в max-heap.
Принцип: сравнение родителя с потомками и восстановление свойства кучи.
"""
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(arr, n, largest)
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"Пирамидальная сортировка: {heap_sort(numbers.copy())}")
3. Сравнительная таблица алгоритмов сортировки
| Алгоритм | Принцип работы | Лучший случай | Средний случай | Худший случай | Память | Устойчивость | Когда использовать |
|---|---|---|---|---|---|---|---|
| Пузырьковая | Сравнение и обмен соседних элементов | O(n) | O(n²) | O(n²) | O(1) | Да | Только для обучения |
| Выбором | Поиск минимума в неотсортированной части | O(n²) | O(n²) | O(n²) | O(1) | Нет | Маленькие массивы |
| Вставками | Вставка элементов в отсортированную часть | O(n) | O(n²) | O(n²) | O(1) | Да | Почти отсортированные или маленькие массивы |
| Быстрая | Разделяй и властвуй с опорным элементом | O(n log n) | O(n log n) | O(n²) | O(log n) | Нет | Общего назначения |
| Слиянием | Разделяй и властвуй со слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | Да | Когда нужна стабильность |
| Пирамидальная | Использование структуры "куча" | O(n log n) | O(n log n) | O(n log n) | O(1) | Нет | Когда важна экономия памяти |
| Timsort | Гибрид слияния и вставок | O(n) | O(n log n) | O(n log n) | O(n) | Да | Встроенный в Python |
4. Практические рекомендации
4.1. Выбор алгоритма для конкретной задачи
- В 99% случаев: используйте встроенные sort() или sorted() — они оптимальны и реализованы на C
- Маленькие массивы (до 50 элементов): сортировка вставками может быть быстрее из-за низких накладных расходов
- Почти отсортированные данные: сортировка вставками или Timsort
- Когда важен худший случай: сортировка слиянием или пирамидальная
- Ограниченная память: пирамидальная сортировка или быстрая сортировка на месте
- Требуется стабильность: сортировка слиянием или вставками
4.2. Практический пример: сравнение производительности
import time
import random
def test_sorting_algorithm(algorithm, arr, name):
"""Тестирование времени выполнения алгоритма сортировки."""
arr_copy = arr.copy()
start_time = time.time()
algorithm(arr_copy)
end_time = time.time()
print(f"{name}: {end_time - start_time:.6f} секунд")
return arr_copy
# Создаем тестовые данные
test_data_small = [random.randint(1, 1000) for _ in range(1000)]
test_data_large = [random.randint(1, 10000) for _ in range(5000)]
print("Сравнение на массиве из 1000 элементов:")
test_sorting_algorithm(sorted, test_data_small, "Встроенная sorted()")
test_sorting_algorithm(bubble_sort, test_data_small, "Пузырьковая")
test_sorting_algorithm(quick_sort, test_data_small, "Быстрая")
4.3. Сортировка сложных структур данных
# Сортировка списка словарей
students = [
{"name": "Анна", "grade": 85, "age": 20},
{"name": "Борис", "grade": 92, "age": 19},
{"name": "Анна", "grade": 78, "age": 22},
{"name": "Иван", "grade": 95, "age": 21}
]
# Сортировка по нескольким ключам
sorted_students = sorted(students, key=lambda x: (x["name"], -x["grade"], x["age"]))
print("Студенты, отсортированные по имени, оценке (по убыванию) и возрасту:")
for student in sorted_students:
print(f"{student['name']}: оценка {student['grade']}, возраст {student['age']}")
# Использование operator.itemgetter для повышения производительности
from operator import itemgetter
sorted_by_grade = sorted(students, key=itemgetter('grade'), reverse=True)
5. Важные понятия
5.1. Устойчивость сортировки (Stability)
Устойчивая сортировка сохраняет относительный порядок элементов с одинаковыми ключами. Например, если сортируем по фамилии, а потом по имени, устойчивая сортировка сохранит алфавитный порядок по имени для одинаковых фамилий.
5.2. In-place vs Out-of-place
- In-place алгоритмы: используют O(1) дополнительной памяти (пузырьковая, выбором, вставками, пирамидальная)
- Out-of-place алгоритмы: требуют дополнительной памяти O(n) или более (слиянием, большинство реализаций быстрой)
5.3. Адаптивность
Адаптивный алгоритм работает быстрее на уже частично отсортированных данных (сортировка вставками, пузырьковая, Timsort).
Заключение
Понимание различных алгоритмов сортировки важно для:
- Выбора оптимального подхода для конкретной задачи
- Оптимизации производительности в критических участках кода
- Прохождения технических собеседований
- Развития алгоритмического мышления
Для практической работы в Python почти всегда используйте встроенные sort() и sorted(), так как они:
- Реализованы на C и очень быстры
- Используют адаптивный алгоритм Timsort
- Поддерживают ключевые функции и обратную сортировку
- Гарантируют стабильность
Однако понимание принципов работы различных алгоритмов поможет вам стать более компетентным разработчиком и эффективно решать специфические задачи, где стандартные подходы могут быть неоптимальны.