Документация не гарантирует этого. Есть ли другое место, где оно задокументировано?
Я предполагаю, что он может быть стабильным, поскольку метод сортировки в списках гарантированно стабилен (Примечания 9-й пункт: "Начиная с Python 2.3, метод sort() гарантированно стабилен" ), и отсортированный функционально схож. Тем не менее, я не могу найти какой-либо окончательный источник, который так говорит.
Цель: мне нужно сортировать на основе первичного ключа, а также вторичного ключа в случаях, когда первичный ключ равен в обеих записях. Если sorted() гарантированно стабилен, я могу сортировать по второстепенному ключу, а затем сортировать по первому ключу и получать нужный мне результат.
PS: Чтобы избежать путаницы, я использую стабильное значение в смысле "сортировка стабильна, если она не позволяет изменить относительный порядок элементов, сравнивающих одинаковые".
Да, намерение руководства действительно гарантирует, что sorted является стабильным и, действительно, использует тот же алгоритм, что и метод sort. Я действительно понимаю, что документы не на 100% понятны об этом удостоверении; doc-патчи всегда с радостью принимаются!
Они стабильны.
Кстати: вы иногда можете игнорировать знание того, являются ли сортировка и сортировка стабильными, комбинируя многопроходную сортировку в однопроходной.
Например, если вы хотите сортировать объекты на основе их атрибутов last_name, first_name, вы можете сделать это за один проход:
sorted_list= sorted(
your_sequence_of_items,
key= lambda item: (item.last_name, item.first_name))
используя сравнение кортежей.
Этот ответ, как есть, охватывает первоначальный вопрос. Для дальнейших вопросов, связанных с сортировкой, существует инструкция по сортировке Python.
В то же время документация изменилась (соответствующая фиксация), и текущая документация, sorted явно, гарантирует:
Встроенная функция
sorted()гарантирована стабильностью. Сорт стабилен, если он не позволяет изменить относительный порядок элементов, сравниваемых равными - это полезно для сортировки в несколько проходов (например, сортировка по отделам, затем по классу зарплаты).
Эта часть документации была добавлена в Python 2.7 и Python 3.4 (+), поэтому любая совместимая реализация этой языковой версии должна иметь стабильную sorted.
Обратите внимание, что для CPython list.sort был стабильным с Python 2.3
- Тим Петерс переписал свою реализацию
list.sort()- это "стабильная сортировка" (равные входы отображаются в том же порядке на выходе) и быстрее, чем раньше.
Я не уверен на 100% sorted, в настоящее время он просто использует list.sort, но я не проверял историю для этого. Но, скорее всего, он "всегда" использовал list.sort.
"What New" docs для Python 2.4 эффективно определяют, что sorted() сначала создает список, а затем вызывает sort() на этом, предоставляя вам необходимую гарантию, но не в "официальных" документах. Вы также можете просто проверить источник, если вы действительно обеспокоены.
Теперь в документе Python 3.6 для сортировки указано, что
Сорта гарантированно стабильны
Кроме того, в этом документе есть ссылка на стабильный Timsort, в котором говорится, что
Timsort был стандартным алгоритмом сортировки Python с версии 2.3