Сортировка в Python: алгоритмы, работа с функциями sort() и sorted(), примеры

Python превращает процесс сортировки в простую и понятную задачу. Благодаря встроенным функциям и продуманным алгоритмам, разработчики могут легко управлять хаосом в данных, задавая такой порядок, какой нужен проекту. Но за этой простотой скрывается мощный механизм, который заслуживает внимания. Какая сортировка используется в Python и как это работает, будем разбираться в статье.

Как работает сортировка в Python: основные подходы

Полезные инструменты для сортировки в Python

Сортировка данных в Python — это больше, чем просто удобство. Это результат сочетания мощного алгоритма Timsort, продуманной архитектуры и гибкости встроенных инструментов. Чтобы не тратить время на ручную реализацию алгоритмов сортировки в Python вроде «пузырька» или «быстрой сортировки», можно решать задачи, используя готовые функции. Они помогут упорядочить данные (в основном числовые) в порядке возрастания или убывания.

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

Основные инструменты для сортировки

Функция sorted()

Подходит для любых итерируемых объектов, будь то список, строка или множество.
Возвращает новый список, оставляя оригинал без изменений.

2. Метод .sort()

Применим только для работы со списками.
Видоизменяет исходный порядок элементов в списке.
Экономит память, если создание новых объектов нежелательно.

Особенности Timsort

Скорость: в худшем случае алгоритм работает за O(n log(n)) — линейно-логарифмическая сложность эффективной сортировки, но если данные частично отсортированы, производительность приближается к линейной.
Стабильность: порядок элементов с одинаковыми значениями сохраняется, что особенно важно для сложных структур данных.
Адаптивность: Timsort подстраивается под особенности данных, поэтому сортировка будет эффективной при любых условиях.

Гибкая работа и простая настройка

Sorted() и .sort() поддерживают несколько необязательных параметров:

key — принимает функцию или метод, который используется для указания любых подробных критериев сортировки, так называемый ключ сортировки.
reverse — указывает, как будет список отсортирован. Он принимает логическое значение: True или False. Элементы сортируются по возрастанию по умолчанию.

Как работают эти функции

Рассмотрим принцип работы sorted():

numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = sorted(numbers)
print(sorted_numbers)   # [1, 2, 5, 5, 6, 9]

А так выглядит метод sort() в деле:

numbers = [5, 2, 9, 1, 5, 6]
numbers.sort()
print(numbers)    # [1, 2, 5, 5, 6, 9]

Как видите, результат одинаковый, но подходы различаются.

Теперь разберем пример с использованием параметров key и reverse:

numbers = [-5, 3, -2, 1, 4]
sorted_numbers = sorted(numbers, key=abs, reverse=True)
print(sorted_numbers)  # [-5, 4, 3, -2, 1]

Здесь данные отсортированы по абсолютной величине — функция abs возвращает абсолютное значение числа.

Сортировка списка по ключу в Python — пользовательская логика

Функция key берет элемент из списка или другого итерируемого объекта и возвращает то, что нужно использовать для сравнения. Например:

data = ["apple", "banana", "cherry"]
sorted_data = sorted(data, key=len) #Сортируем по длине слов
print(sorted_data)  # ['apple', 'cherry', 'banana']

Здесь key=len говорит: «Сравниваем элементы по их длине». Как результат — получаем порядок от самого короткого слова к самому длинному.

Иногда «обычное» возрастание не подходит. Допустим, нужно отсортировать числа по сумме цифр. Это можно сделать с помощью указания собственной логики.

numbers = [111, 42, 9, 33]
sorted_numbers = sorted(numbers, key=lambda x: sum(int(digit) for digit in str(x)))
print(sorted_numbers)  # [9, 33, 42, 111]

Здесь Python сортирует числа, учитывая сумму их цифр. Например, для числа 111 сумма равна 3 (1+1+1), а для 42 — 6 (4+2).

Задавая ключ параметром key, можно также отсортировать данные по возрасту в обратном порядке.

people = [("Alice", 30), ("Bob", 25), ("Charlie", 35)]
sorted_people = sorted(people, key=lambda person: person[1], reverse=True)
print(sorted_people)  # [('Charlie', 35), ('Alice', 30), ('Bob', 25)]

Python позволяет использовать пользовательские функции для более сложных логик сортировки. Так можно создать функцию для сравнения элементов и использовать ее для сортировки по убыванию. Пример:

def custom_sort(x):
    return -x  # Меняем знак, чтобы элементы шли по убыванию
numbers = [5, 1, 3, 2]
sorted_numbers = sorted(numbers, key=custom_sort)
print(sorted_numbers)  # Вывод: [5, 3, 2, 1]

Как сортируются различные итерируемые объекты

Python позволяет выполнить сортировку не только списков, но и других итерируемых объектов: строк, множеств, словарей и даже пользовательских классов.

Сортировка строк

Сортировка в Python предполагает, что строки рассматриваются как последовательность символов. Таким образом строка разбивается на отдельные буквы в алфавитном порядке по умолчанию:

text = "python"
sorted_text = sorted(text)
print(''.join(sorted_text))    # "hnopty"

При этом sorted() не сохраняет изначальную строку, а возвращает список символов. Чтобы вернуть строку, используйте join().

Если строка содержит буквы разного регистра, сначала сортируются заглавные, а затем строчные.

mixed_text = "Python"
print(''.join(sorted(mixed_text)))   # Phnoty

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

Множества в Python — это коллекции, которые хранят уникальные элементы без какого-либо порядка. Поскольку множества не упорядочены, сортировать их напрямую нельзя. Функция sorted() сама приводит множества в список.

data = {3, 1, 4, 1, 5, 9}
sorted_data = sorted(data)
print(sorted_data)    # [1, 3, 4, 5, 9]

Упорядоченные множества также легко возвращать в исходный тип, если необходимо.

Сортировка словарей

Сама по себе эта задача интересная, потому что словари хранят порядок добавления элементов, но сортировать их можно по-разному: по ключам, значениям и даже по какому-то сложному правилу.

Сортировка по ключам

Для сортировки словаря по ключам, можно использовать функцию sorted(). Она вернет список упорядоченных ключей.

data = {"c": 3, "a": 1, "b": 2}
sorted_keys = sorted(data)
print(sorted_keys)     # ['a', 'b', 'c']

Если нужен именно отсортированный словарь, то преобразуем его:

sorted_dict = {key: data[key] for key in sorted(data)}
print(sorted_dict)    # {'a': 1, 'b': 2, 'c': 3}

Сортировка по значениям

Для этого типа сортировки нужно сказать Python, что ориентироваться следует на значения. Это можно сделать через key:

data = {"c": 3, "a": 1, "b": 2}
sorted_by_values = {key: value for key, value in sorted(data.items(), key=lambda item: item[1])}
print(sorted_by_values)    # {'a': 1, 'b': 2, 'c': 3}

Здесь sorted() сортирует пары (ключ, значение) на основе значения — второго элемента кортежа item [1].

Если необходимо отсортировать словарь в убывающем порядке, добавьте параметр reverse=True. Например:

sorted_by_values_desc = {key: value for key, value in sorted(data.items(), key=lambda item: item[1], reverse=True)}
print(sorted_by_values_desc)    # {'c': 3, 'b': 2, 'a': 1}

Сортировка кортежей

Кортежи в Python — это неизменяемые списки. Сами кортежи изменить нельзя, но их можно упорядочить в виде нового списка. Если у вас коллекция кортежей, можно сортировать ее по разным критериям: по первому, второму элементу или по какой-то вычисляемой характеристике.

Если у вас один кортеж, например:

data = (5, 2, 9, 1, 7)

Чтобы отсортировать его применим sorted():

sorted_tuple = tuple(sorted(data))
print(sorted_tuple)    # (1, 2, 5, 7, 9)

Когда у вас коллекция из кортежей, к примеру:

data = [(3, 'яблоко'), (1, 'банан'), (2, 'груша')]

Можно сортировать их по первому элементу (числу) по умолчанию:

sorted_data = sorted(data)
 print(sorted_data)	# [(1, 'банан'), (2, 'груша'), (3, 'яблоко')]

Если нужно сортировать по второму элементу, используйте параметр key:

sorted_by_second = sorted(data, key=lambda x: x[1])
print(sorted_by_second)  # [(1, 'банан'), (3, 'яблоко'), (2, 'груша')]

Пользовательские объекты

Иногда классы и объекты, представляющие, например, людей, автомобили, заказы, нужно упорядочить по определенным критериям: возраст, цена или дата. Так sorted() может работать с объектами так же, как с числами и строками, если указать, по какому критерию сортировать.

class Student:
    def __init__(self, name, grade):
        self.name = name
        self.grade = grade



students = [Student("Alice", 90), Student("Bob", 80), Student("Eve", 95)]
students.sort(key=lambda student: student.grade)
for student in students:
    print(student.name, student.grade)

Результат:

Bob 80
Alice 90
Eve 95

Сортировка списка повозрастанию вPython

Для сортировки по возрастанию можно использовать несколько встроенных методов: sorted() или .sort(), а также задавать дополнительные параметры с key

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

Выше разобрали ключевые инструменты, которые программисты используют для сортировки. Так у разработчика есть как минимум два варианта: работать с исходным списком или создать новый. Рассмотрим пример с sorted():

numbers = [8, 3, 7, 1, 5]
sorted_numbers = sorted(numbers)
print(sorted_numbers)   # [1, 3, 5, 7, 8]
print(numbers)   # [8, 3, 7, 1, 5] — оригинал не изменился

Сортировка с учетом разных типов данных

Если список содержит элементы разных типов, например, числа и строки, метод .sort() не будет работать, так как Python не знает, как сравнить, скажем, число 5 и строку "apple". Однако можно предварительно преобразовать все элементы в один тип.
Например:

mixed = ["2", 1, "3", 4]
sorted_mixed = sorted(mixed, key=int)  # Все элементы приводятся к числу
print(sorted_mixed)  # [1, "2", "3", 4]

Сортировка списка по убыванию в Python

Помимо сортировки по возрастанию, которая происходит по умолчанию, разработчик может отсортировать данные в порядке убывания

Это процесс упорядочивания элементов от наибольшего к наименьшему. Такая сортировка будет полезна, например, чтобы сначала вывести самые большие значения, самые высокие рейтинги или последние даты. В Python сортировка по убыванию реализуется с помощью тех же инструментов, что и сортировка по возрастанию, но с параметром reverse=True. Пример:

numbers = [5, 1, 3, 2]
numbers.sort(reverse=True)  # Сортируем по убыванию
print(numbers)  # [5, 3, 2, 1]

Что такое стабильность сортировки ипочему это важно

Стабильность сортировки — это концепция, которая отвечает на вопрос: сохранится ли относительный порядок одинаковых элементов после сортировки? В Python, начиная с версии 2.3, сортировка стабильна, и это одно из ее скрытых достоинств.

Что значит «стабильная»

Представьте, у вас есть список студентов, где каждый — это пара (имя, оценка):

students = [("Alice", 90), ("Bob", 85), ("Charlie", 90)]

Если вы отсортируете их по оценке:

sorted_students = sorted(students, key=lambda x: x[1])

Результат будет:

[("Bob", 85), ("Alice", 90), ("Charlie", 90)]

Обратите внимание: "Alice" осталась перед "Charlie", хотя у них одинаковая оценка. Это потому, что Python сохраняет порядок, в котором элементы уже были расположены в исходном списке.

Почему это важно

Многоступенчатая сортировка. Стабильность делает многоуровневую сортировку интуитивной. Например, вы хотите сначала отсортировать студентов по имени, а затем по оценке:

students = [("Charlie", 90), ("Alice", 85), ("Bob", 85)]
students_by_name = sorted(students, key=lambda x: x[0])  # По имени
final_sort = sorted(students_by_name, key=lambda x: x[1])  # По оценке

Результат:

[("Alice", 85), ("Bob", 85), ("Charlie", 90)]

Стабильность гарантирует, что порядок по имени внутри одинаковых оценок сохранится.

2. Работа с данными в реальном мире. Когда данные уже частично упорядочены, стабильная сортировка не ломает существующий порядок, что может быть критически важно, например, в бухгалтерии, логистике или анализе данных.

Когда стабильность — спасение

Вложенные списки, сложные структуры данных.
Многоуровневая сортировка.
Любой случай, когда порядок одинаковых элементов важен для интерпретации данных.

Разница между .sort() и sorted()

Выше рассмотрели основные методы сортировки в Python и их особенности. Подытожим и выделим главные отличия:

Тип функции. Sorted() — универсальная функция, которая работает с любыми итерируемыми объектами. Метод .sort() применяют только к спискам.
Изменение данных. Sorted() не изменяет оригинал, а создает новый список с сортировкой. А .sort() меняет исходный список на месте и возвращает None.
Когда использовать. Если хотите сохранить исходный объект нетронутым, выбирайте sorted(). Когда нужно отсортировать список без создания копии и важна производительность, подойдет .sort().

Сортировка в Python превращает хаос в порядок и работает с любой сложностью. Но за, казалось бы, несложными примерами скрывается глубокий мир алгоритмов, оптимизаций и возможностей, который стоит изучить.

Если вам понравилось, как Python делает сложное простым, самое время пойти дальше и углубиться в мир программирования с курсом по Python-разработке от ProductStar. С ним вы изучите основы: от работы с данными до создания сложных приложений, а также освоите необходимые инструменты и навыки. И, быть может, вскоре вы напишете собственный алгоритм, который изменит правила игры.

Статья написана с участием эксперта — Данилы Логунова, разработчика РБК Pro.