Функция Python sorted () гарантированно стабильна?

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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

Этот ответ, как есть, охватывает исходный вопрос. Для дальнейших вопросов, связанных с сортировкой, есть Python Sorting How-To .

Answer 3

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

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

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

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

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

Я не уверен на 100% в sorted, сейчас он просто использует list.sort, но я не проверял историю для этого. Но вполне вероятно, что он «всегда» использовал list.sort.

Answer 4

Документ Python 3.6 о сортировке теперь утверждает, что

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

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

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

Answer 5

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