Является ли функция python sorted() гарантией стабильности?

Документация не гарантирует этого. Есть ли другое место, где оно задокументировано?

Я предполагаю, что он может быть стабильным, поскольку метод сортировки в списках гарантированно стабилен (Примечания 9-й пункт: "Начиная с Python 2.3, метод sort() гарантированно стабилен" ), и отсортированный функционально схож. Тем не менее, я не могу найти какой-либо окончательный источник, который так говорит.

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

PS: Чтобы избежать путаницы, я использую стабильное значение в смысле "сортировка стабильна, если она не позволяет изменить относительный порядок элементов, сравнивающих одинаковые".

Ответ 1

Да, намерение руководства действительно гарантирует, что sorted является стабильным и, действительно, использует тот же алгоритм, что и метод sort. Я действительно понимаю, что документы не на 100% понятны об этом удостоверении; doc-патчи всегда с радостью принимаются!

Ответ 2

Они стабильны.

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

Например, если вы хотите сортировать объекты на основе их атрибутов last_name, first_name, вы можете сделать это за один проход:

sorted_list= sorted(
    your_sequence_of_items,
    key= lambda item: (item.last_name, item.first_name))

используя сравнение кортежей.

Этот ответ, как есть, охватывает первоначальный вопрос. Для дальнейших вопросов, связанных с сортировкой, существует инструкция по сортировке Python.

Ответ 3

В то же время документация изменилась (соответствующая фиксация), и текущая документация, sorted явно, гарантирует:

Встроенная функция sorted() гарантирована стабильностью. Сорт стабилен, если он не позволяет изменить относительный порядок элементов, сравниваемых равными - это полезно для сортировки в несколько проходов (например, сортировка по отделам, затем по классу зарплаты).

Эта часть документации была добавлена в Python 2.7 и Python 3.4 (+), поэтому любая совместимая реализация этой языковой версии должна иметь стабильную sorted.

Обратите внимание, что для CPython list.sort был стабильным с Python 2.3

Тим Петерс переписал свою реализацию list.sort() - это "стабильная сортировка" (равные входы отображаются в том же порядке на выходе) и быстрее, чем раньше.

Я не уверен на 100% sorted, в настоящее время он просто использует list.sort, но я не проверял историю для этого. Но, скорее всего, он "всегда" использовал list.sort.

Ответ 4

"What New" docs для Python 2.4 эффективно определяют, что sorted() сначала создает список, а затем вызывает sort() на этом, предоставляя вам необходимую гарантию, но не в "официальных" документах. Вы также можете просто проверить источник, если вы действительно обеспокоены.

Ответ 5

Теперь в документе Python 3.6 для сортировки указано, что

Сорта гарантированно стабильны

Кроме того, в этом документе есть ссылка на стабильный Timsort, в котором говорится, что

Timsort был стандартным алгоритмом сортировки Python с версии 2.3