Czy funkcja sortowana () w języku Python jest stabilna?

Dokumentacja nie gwarantuje. Czy jest jakieś inne miejsce, które jest udokumentowane?

Domyślam się, że może być stabilna, ponieważ metoda sortowania na listach jest gwarantowana jako stabilna (Uwagi 9 punkt: „Począwszy od Pythona 2.3, metoda sort () jest stabilna”), a sortowanie jest funkcjonalnie podobne. Jednak nie jestem w stanie znaleźć żadnego ostatecznego źródła, które by to mówiło.

Cel: muszę sortować na podstawie klucza podstawowego, a także klucza pomocniczego w przypadkach, gdy klucz podstawowy jest taki sam w obu rekordach. Jeśli gwarantujemy, że funkcja sortowania () jest stabilna, mogę posortować dane według klucza dodatkowego, a następnie posortować dane według klucza podstawowego i uzyskać wynik, którego potrzebuję.

PS: Aby uniknąć nieporozumień, używam stabilnego w znaczeniu „sort jest stabilny, jeśli gwarantuje, że nie zmieni się względnej kolejności elementów, które porównują równe sobie”.

Tak, intencją podręcznika jest rzeczywiście zagwarantowanie, że sortedjest stabilny i że używa dokładnie tego samego algorytmu, co sortmetoda. Zdaję sobie sprawę, że doktorzy nie są w 100% jasni co do tej tożsamości; doc patche są zawsze szczęśliwie akceptowane!

Są stabilne .

Przy okazji: czasami możesz zignorować wiedzę, czy sortowanie i sortowanie są stabilne, łącząc sortowanie wieloprzebiegowe z sortowaniem jednoprzebiegowym.

Na przykład, jeśli chcesz rodzaju obiektów na podstawie ich last_name, first_nameatrybutów, można to zrobić w jednym przebiegu:

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

korzystając z porównania krotek.

Ta odpowiedź, jak jest, obejmuje pierwotne pytanie. Więcej pytań związanych z sortowaniem można znaleźć w poradniku na temat sortowania w Pythonie .

Dokumentacja zmieniona w międzyczasie ( odpowiednie zobowiązanie ), a obecna dokumentacja sortedwyraźnie to gwarantuje:

Wbudowana sorted()funkcja gwarantuje stabilność. Sortowanie jest stabilne, jeśli gwarantuje, że nie zmieni względnej kolejności elementów, które porównują się równo - jest to pomocne przy sortowaniu w wielu zdaniach (na przykład sortowanie według działu, a następnie według poziomu wynagrodzenia).

Ta część dokumentacji została dodana do Pythona 2.7 i Pythona 3.4 (+), więc każda zgodna implementacja tej wersji językowej powinna mieć stabilną wersję sorted.

Zauważ, że w przypadku CPython list.sortbył stabilny od czasu Pythona 2.3

• Tim Peters przepisał swoją list.sort()implementację - ta jest „stabilnym sortowaniem” (równe dane wejściowe pojawiają się w tej samej kolejności na wyjściu) i szybciej niż poprzednio.

Nie jestem pewien w 100% sorted, obecnie jest to proste użycie list.sort, ale nie sprawdzałem historii. Ale jest prawdopodobne, że był używany „zawsze” list.sort.

Dokumentacja „Co nowego” dla Pythona 2.4 skutecznie wskazuje, że sort () najpierw tworzy listę, a następnie wywołuje na niej sort (), zapewniając gwarancję, której potrzebujesz, chociaż nie ma jej w „oficjalnych” dokumentach. Jeśli naprawdę się martwisz, możesz po prostu sprawdzić źródło.

Dokument Python 3.6 dotyczący sortowania stwierdza teraz, że

Sortowanie gwarantuje stabilność

Ponadto w dokumencie tym znajduje się odsyłacz do stabilnego Timsort , który to stwierdza

Timsort jest standardowym algorytmem sortowania Pythona od wersji 2.3