Навигация по странице
Сортировка данных
Один из фундаментальных процессов в обработке информации – это сортировка. Представьте себе, что вы пытаетесь найти определенную книгу в библиотеке, где тысячи различных литературных произведений расставлены в абсолютно случайном порядке. Такая задача может занять часы!
Однако, если все книги будут упорядочены по алфавиту или тематическим разделам, поиск займет всего несколько минут. Этот простой пример иллюстрирует ключевую ценность сортировки: она превращает хаос в структуру, делая работу с данными эффективной и осмысленной.
В нашей повседневной жизни мы постоянно сталкиваемся с отсортированными данными: списки контактов в телефоне, упорядоченные по алфавиту; транзакции в банковском приложении, отсортированные по дате; товары в интернет-магазине, ранжированные по количеству отзывов или цене.
Сортировка применяется практически везде, где требуется каким-либо образом систематизировать информацию для облегчения поиска, анализа или представления данных.
В мире программирования сортировка имеет еще более широкое применение:
- В аналитике данных — для выявления трендов, обнаружения выбросов или подготовки данных к визуализации
- В поисковых системах — для ранжирования результатов по релевантности
- В базах данных — для оптимизации запросов и индексирования
- В разработке игр — для определения порядка отрисовки объектов или создания рейтинговых таблиц
- В финансовых приложениях — для ранжирования транзакций, инвестиций или потенциальных рисков
В Python, как в одном из самых популярных языков для работы с данными, уже встроен функционал для сортировки данных. В этой статье мы сосредоточимся на изучении этих встроенных в Python функций, которые являются основой для большинства задач сортировки.
Мы научимся работать с ключевыми параметрами из этих функций, а также на практике применять лямбда-выражения для сортировки сложных структур данных.
После прочтения этой статьи вы не только научитесь эффективно применять функции сортировки в своих проектах, но и глубже поймете принципы работы с данными в Python в целом. Давайте погрузимся в мир сортировки и раскроем всю мощь этого фундаментального инструмента программирования.
Функции сортировки
Для сортировки данных в Python по умолчанию встроена функция sorted() и метод списков sort(). Давайте разберёмся, чем они отличаются, и как правильно их применять.
Функция sorted()
Начнём с функции sorted(). Она позволяет упорядочить элементы какой-либо коллекции. Данная функция возвращает отсортированную в порядке возрастания копию исходной коллекции в виде списка.
Функция sorted() имеет следующий синтаксис:
sorted(iterable, key=None, reverse=False)
Где:
- iterable — коллекция, которую нужно отсортировать (список, кортеж, строка, словарь, множество и т.д.)
- key — необязательный аргумент, функция, которая применяется к каждому элементу перед сравнением (определяет критерий сортировки)
- reverse — необязательный логический параметр, определяющий порядок сортировки (по умолчанию False, что означает сортировку по возрастанию)
Давайте продемонстрируем её работу с различными типами коллекций. Начнём с самого базового типа – со списка. Отсортируем список целых чисел в порядке возрастания.
unsorted_list = [4, 3, 2, 5, 1]
sorted_list = sorted(unsorted_list)
print(f'Исходный список: {unsorted_list}')
print(f'Отсортированный: {sorted_list}')
>>>Исходный список: [4, 3, 2, 5, 1]
>>>Отсортированный: [1, 2, 3, 4, 5]
С кортежами и множествами все будет аналогично – на выходе получим отсортированный по возрастанию список целых чисел. Но совсем иначе обстоит работа сортировки со строками.
Символы в строке будут отсортированы в лексикографическом порядке, то есть в порядке их следования в Unicode (сначала идут спецсимволы, затем – заглавные латинские буквы, после них – несколько знаков препинания, строчные буквы и все остальные символы).
Для примера отсортируем строку случайных символов: «ZV-bc_aA».
unsorted_str = 'ZV-bc_aA'
sorted_list = sorted(unsorted_str)
print(f'Отсортированный список: {sorted_list}')
На выходе мы получим список символов, которые расставлены в соответствии с их кодом в Unicode: «[‘-‘, ‘A’, ‘V’, ‘Z’, ‘_’, ‘a’, ‘b’, ‘c’]».
Если вам нужна именно отсортированная строка, а не список, то можно объединить все элементы списка в строку с помощью метода join():
unsorted_str = 'ZV-bc_aA'
sorted_list = sorted(unsorted_str)
sorted_str = ''.join(sorted_list)
print(f'Исходная строка: {unsorted_str}')
print(f'Отсортированная строка: {sorted_str}')
>>>Исходная строка: ZV-bc_aA
>>>Отсортированная строка: -AVZ_abc
Но куда интереснее обстоит дело с сортировкой словарей. По умолчанию функция sorted() позволяет сортировать словарь только по ключам. Например, у нас в словаре ключами являются уникальные идентификаторы (ID) пользователей, а значениями – их имена.
Отсортируем словарь по возрастанию значения ключей:
unsorted_dict = {4: 'Мария',
2: 'Иван',
1: 'Павел',
3: 'Алиса'}
sorted_dict = sorted(unsorted_dict)
print(f'Отсортированный список: {sorted_dict}')
>>>Отсортированный список: [1, 2, 3, 4]
Да, это не совсем то, что мы ожидали увидеть после фразы «отсортируем словарь». Но это поведение вполне очевидно – функция sorted() возвращает только отсортированный список. При работе со словарями нам необходимо применять эту функцию для сортировки ключей или значений словаря, а затем создавать новый словарь, но уже с нужным порядком следования элементов.
Совсем скоро мы научимся этому, но для начала нам необходимо разобраться с методом sort() и с использованием параметра key для более продвинутой сортировки.
Метод sort()
В отличие от функции sorted(), метод sort() является методом списков в Python, что и означает его главное отличие — он работает исключительно со списками и не может быть применен к другим итерируемым объектам, таким как кортежи, строки или словари.
Ключевая особенность метода sort() состоит в том, что он выполняет сортировку «на месте». Это означает, что метод изменяет исходный список вместо создания нового отсортированного списка.
После вызова метода sort() оригинальный список будет переупорядочен согласно указанным критериям, а метод вернет None. Данное поведение представляет собой фундаментальное различие с функцией sorted(), которая всегда возвращает новый список и сохраняет исходный объект неизменным.
Давайте рассмотрим работу этого метода на все том же примере с сортировкой списка целых чисел. Обратите внимание, что теперь мы не сохраняем результат вызова этого метода в отдельную переменную, как раньше это делали с «sorted_list». Нам достаточно просто применить этот метод к нашему списку.
num_list = [4, 3, 2, 5, 1]
print(f'Исходный список: {num_list}')
num_list.sort()
print(f'Отсортированный: {num_list}')
>>>Исходный список: [4, 3, 2, 5, 1]
>>>Отсортированный: [1, 2, 3, 4, 5]
Когда же стоит использовать метод sort() вместо функции sorted()? Этот метод предпочтителен в следующих ситуациях:
- Когда вам не нужно сохранять оригинальную последовательность элементов списка, и вы хотите работать с тем же объектом списка.
- Когда важна эффективность использования памяти — sort() более экономичен с точки зрения памяти, поскольку не создает дополнительную копию списка, что особенно важно при работе с большими наборами данных.
- Когда сортировка является промежуточным шагом в обработке данных, и вы продолжите работать с тем же списком.
- Когда вы хотите упростить код, избегая создания дополнительных переменных для хранения отсортированного списка.
Параметры key и reverse
Переходим к работе с параметрами функции sorted(). Аналогичные будут применимы и для метода sort(), но мы будем работать именно с sorted(), ввиду того, что далее будет часть примеров, в которых мы будем сортировать словари.
Начнём с самого простого – параметр reverse со значением True позволяет «развернуть» направление сортировки. То есть если изначально сортировка идёт по возрастанию, то при передаче аргумента «reverse=True» функция будет сортировать элементы в порядке убывания.
Для примера отсортируем список целых чисел в порядке убывания:
unsorted_list = [4, 3, 2, 5, 1]
sorted_list = sorted(unsorted_list, reverse=True)
print(f'Исходный список: {unsorted_list}')
print(f'Отсортированный: {sorted_list}')
>>>Исходный список: [4, 3, 2, 5, 1]
>>>Отсортированный: [5, 4, 3, 2, 1]
Далее уже посложнее. Параметр key принимает функцию, которая применяется к каждому элементу коллекции перед сравнением. Такая функция еще называется «функция-ключ».
Наглядно работу функции, передаваемой в key, можно рассмотреть на примере сортировки списка по длине строк, входящих в него. Для этого нужно передать в key функцию len() (обратите внимание, что передаётся только название функции, без скобок!):
words = ['шаг', 'в', 'будущее']
sorted_list = sorted(words, key=len)
print(f'Исходный список: {words}')
print(f'Отсортированный: {sorted_list}')
>>>Исходный список: ['шаг', 'в', 'будущее']
>>>Отсортированный: ['в', 'шаг', 'будущее']
Что же здесь произошло? К исходному списку была применена функция len(), которая высчитала количество символов в каждой строке и вернула это количество в виде целых чисел. Можно сказать, что из такого списка «[‘шаг’, ‘в’, ‘будущее’]» мы получили такой: «[3, 1, 7]».
А дальше произошла обычная сортировка целых чисел. То есть из списка «[3, 1, 7]» был получен список «[1, 3, 7]». А для формирования итогового списка строк эти числовые значения были обратно «заменены» на строки: «[‘в’, ‘шаг’, ‘будущее’]».
Рассмотрим еще один пример сортировки с применением функции-ключа. Представим, что нам нужно отсортировать список так, чтобы сначала шли по возрастанию все чётные числа, а только потом нечётные.
Так, а разве у нас есть функция для определения чётности числа? Такой встроенной функции нет, но мы же можем создать лямбда-выражение, результатом которого как раз и будет проверка чётности числа. Вспомним, что такое лямбда-выражения в Python и как они работают.
Лямбда-выражения при сортировке
Лямбда-выражения в Python — это компактный способ создания небольших одноразовых функций «на лету», без необходимости их формального определения с использованием ключевого слова def.
Они представляют собой встроенный механизм функционального программирования, который особенно полезен, когда нам нужна простая функция для кратковременного использования, например, в качестве аргумента для функций высшего порядка, таких как sorted(), map(), filter() и других.
Базовый синтаксис лямбда-выражения выглядит следующим образом:
lambda аргументы: выражение
Где:
- lambda — ключевое слово, обозначающее начало анонимной (лямбда) функции
- аргументы — список аргументов, разделенных запятыми (может быть пустым)
- выражение — одиночное выражение, результат которого будет возвращен функцией
Помните, что лямбда-выражение ограничено единственным выражением — в нём нельзя использовать несколько строк кода, операторы ветвления или циклы в их стандартном синтаксисе!
Сравним работу обычной именованной функции для определения чётности числа и лямбда-выражения с тем же функционалом:
# Обычная функция
def is_even(x):
return x % 2 == 0
# Эквивалентная лямбда-функция
is_even_lambda = lambda x: x % 2 == 0
print(is_even(6))
print(is_even_lambda(4))
>>>True
>>>True
Теперь вернёмся к нашей задаче по сортировке чисел по чётности и возрастанию. Нам нужно создать функцию-ключ, которая будет возвращать кортеж из двух элементов: первый элемент определяет приоритет чётности (0 для четных, 1 для нечетных), а второй элемент — само число для сортировки в пределах своей группы.
Для определения приоритета чётности числа «x» нам достаточно выражения «x % 2». Для чётных оно будет возвращать ноль (остаток от деления на два будет равен нулю), а для нечётных – единицу.
Вторым элементом кортежа у нас будет само число «x». Кстати, если требуется отсортировать в обратном порядке, то вторым элементом кортежа можно поставить значение «–x».
Получим такую программу для сортировки списка чисел:
nums = [4, 5, 6, 1, 3, 2]
sorted_nums = sorted(nums, key=lambda x: (x % 2, x))
print(f'Исходный список: {nums}')
print(f'Отсортированный: {sorted_nums}')
>>>Исходный список: [4, 5, 6, 1, 3, 2]
>>>Отсортированный: [2, 4, 6, 1, 3, 5]
Теперь вернёмся к сортировке словарей. Важно понимать, что словари в Python до версии 3.7 были неупорядоченными коллекциями, а начиная с Python 3.7 словари сохраняют порядок вставки элементов. Так что обращайте внимание на используемую версию интерпретатора Python при работе со словарями!
Сам по себе словарь не может быть отсортирован по значениям ключей или значений. Давайте рассмотрим, как можно создать новые отсортированные словари с помощью функции sorted().
Пусть у нас есть словарь, в котором ключами являются имена учеников, а значениями – их баллы за экзамен. Давайте для начала отсортируем этот словарь по именам в алфавитном порядке.
students = {
'Давид': 85,
'Алиса': 92,
'Василий': 78,
'Юлия': 95,
'Мария': 88
}
# Создаём новый словарь
sorted_by_name = {key: students[key]
for key in sorted(students)}
print("Исходный словарь:")
print(students)
print("\nСловарь, отсортированный по именам:")
print(sorted_by_name)
>>>Исходный словарь:
{'Давид': 85, 'Алиса': 92, 'Василий': 78, 'Юлия': 95, 'Мария': 88}
>>>Словарь, отсортированный по именам:
{'Алиса': 92, 'Василий': 78, 'Давид': 85, 'Мария': 88, 'Юлия': 95}
В этом примере мы используем генератор словаря и функцию sorted() для создания нового словаря, где ключи упорядочены по алфавиту.
Теперь отсортируем этот же словарь по убыванию баллов за экзамен, то есть по убыванию значений этого словаря.
students = {
'Давид': 85,
'Алиса': 92,
'Василий': 78,
'Юлия': 95,
'Мария': 88
}
# Создаём новый словарь
sorted_by_score = dict(sorted(students.items(),
key=lambda item: item[1],
reverse=True))
print("Исходный словарь:")
print(students)
print("\nСловарь, отсортированный по баллам:")
print(sorted_by_score)
>>>Исходный словарь:
{'Давид': 85, 'Алиса': 92, 'Василий': 78, 'Юлия': 95, 'Мария': 88}
>>>Словарь, отсортированный по баллам:
{'Юлия': 95, 'Алиса': 92, 'Мария': 88, 'Давид': 85, 'Василий': 78}
Здесь мы используем метод items() для получения пар «ключ, значение», сортируем их по значению с помощью lambda-функции, а затем преобразуем результат обратно в словарь.
До текущего момента мы не сталкивались с ситуацией, когда в сортируемой последовательности встречаются одинаковые значения. Допустим, у нас есть список с кортежами под каждого ученика: в кортеже содержится имя ученика, его оценка и очерёдность сдачи работы.
Мы хотим, чтобы в итоговом рейтинге учитывалась не только оценка ученика, но и скорость сдачи работы. Например, если два ученика получили за работу оценку 5, то на первом месте будет именно тот, кто сдал эту работу раньше.
Пусть мы получали сданные работы в таком порядке:
- Алиса с оценкой 4
- Борис с оценкой 5
- Виктор с оценкой 4
- Галина с оценкой 3
- Дмитрий с оценкой 5
- Елена с оценкой 3
В коде это можно выразить таким списком кортежей:
students = [
('Алиса', 4),
('Борис', 5),
('Виктор', 4),
('Галина', 3),
('Дмитрий', 5),
('Елена', 3)
]
На «отлично» работу сдали двое: Борис и Дмитрий. Но Борис сдал работу раньше, чему и соответствует позиция его кортежа в списке students (второй элемент).
students = [
('Алиса', 4),
('Борис', 5),
('Виктор', 4),
('Галина', 3),
('Дмитрий', 5),
('Елена', 3)
]
sorted_students = sorted(students,
key=lambda student: student[1],
reverse=True)
print("\nОтсортированный по оценке список:")
for name, grade in sorted_students:
print(f"{name}: оценка {grade}")
>>>Отсортированный по оценке список:
Борис: оценка 5
Дмитрий: оценка 5
Алиса: оценка 4
Виктор: оценка 4
Галина: оценка 3
Елена: оценка 3
Как мы видим, в отсортированном списке сохранился исходный порядок следования элементов: Борис сдал работу раньше Дмитрия, Алиса – раньше Виктора и т.д.
Это говорит нам о стабильности сортировки в Python. Стабильность сортировки — это свойство алгоритма сортировки, означающее, что порядок равных элементов сохраняется после сортировки.
То есть если у нас есть два элемента А и Б с одинаковым значением по ключу сортировки, и А стоял перед Б в исходной последовательности, то после стабильной сортировки А все еще будет стоять перед Б.
Стабильность сортировки критически важна во многих приложениях, особенно при:
- Многоуровневой сортировке — когда данные сортируются последовательно по нескольким критериям.
- Сохранении контекстной информации — когда относительный порядок элементов содержит дополнительную информацию, которую важно сохранить.
- Работе с пользовательскими интерфейсами — когда пользователи ожидают предсказуемого поведения при сортировке таблиц или списков.
Стабильность сортировки особенно полезна при выполнении многоуровневой сортировки в несколько этапов.
Давайте расширим наш рейтинг учеников. Теперь в списке students будут храниться словари следующего формата:
- Имя ученика (ключ name)
- Класс ученика (ключ class)
- Оценка за работу (ключ grade)
Имеем такой список словарей:
students = [
{'name': 'Алиса', 'class': '11А', 'grade': '4'},
{'name': 'Борис', 'class': '11Б', 'grade': '5'},
{'name': 'Виктор', 'class': '11А', 'grade': '4'},
{'name': 'Галина', 'class': '11Б', 'grade': '3'},
{'name': 'Дмитрий', 'class': '11А', 'grade': '5'},
{'name': 'Елена', 'class': '11Б', 'grade': '3'}
]
Сначала отсортируем его по оценке:
students = [
{'name': 'Алиса', 'class': '11А', 'grade': '4'},
{'name': 'Борис', 'class': '11Б', 'grade': '5'},
{'name': 'Виктор', 'class': '11А', 'grade': '4'},
{'name': 'Галина', 'class': '11Б', 'grade': '3'},
{'name': 'Дмитрий', 'class': '11А', 'grade': '5'},
{'name': 'Елена', 'class': '11Б', 'grade': '3'}
]
stage1 = sorted(students,
key=lambda s: s['grade'],
reverse=True)
print("После сортировки по оценке:")
for s in stage1:
print(f"{s['name']}: класс {s['class']}, оценка {s['grade']}")
>>>После сортировки по оценке:
Борис: класс 11Б, оценка 5
Дмитрий: класс 11А, оценка 5
Алиса: класс 11А, оценка 4
Виктор: класс 11А, оценка 4
Галина: класс 11Б, оценка 3
Елена: класс 11Б, оценка 3
Теперь отсортируем этот список по классу. То есть сначала будут ученики 11 «А» класса, затем – 11 «Б».
students = [
{'name': 'Алиса', 'class': '11А', 'grade': '4'},
{'name': 'Борис', 'class': '11Б', 'grade': '5'},
{'name': 'Виктор', 'class': '11А', 'grade': '4'},
{'name': 'Галина', 'class': '11Б', 'grade': '3'},
{'name': 'Дмитрий', 'class': '11А', 'grade': '5'},
{'name': 'Елена', 'class': '11Б', 'grade': '3'}
]
stage1 = sorted(students,
key=lambda s: s['grade'],
reverse=True)
print("После сортировки по оценке:")
for s in stage1:
print(f"{s['name']}: класс {s['class']}, оценка {s['grade']}")
stage2 = sorted(stage1, key=lambda s: s['class'])
print("\nПосле сортировки по классу:")
for s in stage2:
print(f"{s['name']}: класс {s['class']}, оценка {s['grade']}")
>>>После сортировки по оценке:
Борис: класс 11Б, оценка 5
Дмитрий: класс 11А, оценка 5
Алиса: класс 11А, оценка 4
Виктор: класс 11А, оценка 4
Галина: класс 11Б, оценка 3
Елена: класс 11Б, оценка 3
>>>После сортировки по классу:
Дмитрий: класс 11А, оценка 5
Алиса: класс 11А, оценка 4
Виктор: класс 11А, оценка 4
Борис: класс 11Б, оценка 5
Галина: класс 11Б, оценка 3
Елена: класс 11Б, оценка 3
Здесь благодаря стабильности сортировки, студенты в каждом классе остаются отсортированными по оценке после второго этапа сортировки.
Однако есть более компактный способ добиться того же самого эффекта. В современном Python часто вместо последовательной сортировки используется сортировка по кортежу критериев — это гарантирует правильный порядок применения критериев:
students = [
{'name': 'Алиса', 'class': '11А', 'grade': '4'},
{'name': 'Борис', 'class': '11Б', 'grade': '5'},
{'name': 'Виктор', 'class': '11А', 'grade': '4'},
{'name': 'Галина', 'class': '11Б', 'grade': '3'},
{'name': 'Дмитрий', 'class': '11А', 'grade': '5'},
{'name': 'Елена', 'class': '11Б', 'grade': '3'}
]
sorted_students = sorted(students, key=lambda s: (s['class'], -int(s['grade'])))
print("Отсортировано по классу, затем по оценке:")
for s in sorted_students:
print(f"{s['name']}: класс {s['class']}, оценка {s['grade']}")
>>>Отсортировано по классу, затем по оценке:
Дмитрий: класс 11А, оценка 5
Алиса: класс 11А, оценка 4
Виктор: класс 11А, оценка 4
Борис: класс 11Б, оценка 5
Галина: класс 11Б, оценка 3
Елена: класс 11Б, оценка 3
Здесь мы сначала сортируем по классу – сначала 11 «А», потом 11 «Б» – затем по оценке внутри каждого класса.
Для облегчения работы со словарями можно применять методы модуля operator, такие как itemgetter(), attrgetter() и methodcaller(). Но их применению мы уделим время уже в следующих статьях.