Informacje o wbudowanej metodzie sort () w Pythonie

104

Jakiego algorytmu sort()używa metoda wbudowana w Pythonie? Czy można rzucić okiem na kod tej metody?

python algorithm sorting python-internals Johannes
źródło

Oczywiście można spojrzeć na kod metody - Python jest projektem open source. Metoda jest jednak prawdopodobnie zaimplementowana w C, więc będziesz musiał trochę wiedzieć o C, aby nadać jej sens.

Chris Lutz

Czy wersja ma znaczenie?

meder omuraliev

@melder: Nie =) Chcę tylko rzucić okiem na profesjonalny algorytm: P @chris: jak?

Johannes

Pobierz kod źródłowy do interpretera języka Python. Nie wiem, gdzie implementują tę sort()metodę ani jakie jest formatowanie dla interpretera, ale musi gdzieś tam być i założę się, że jest zaimplementowany w C ze względu na obawy o szybkość.

Chris Lutz

Oto przykład jego użycia

Hari Ganesan

Odpowiedzi:

119

Pewnie! Kod jest tutaj , zaczynając od funkcji islti kontynuując przez chwilę QUITE ;-). Jak sugeruje komentarz Chrisa, jest to kod C. Będziesz także chciał przeczytać ten plik tekstowy, aby uzyskać wyjaśnienie tekstowe, wyniki itp.

Jeśli wolisz czytać kod w Javie niż w C, możesz przyjrzeć się implementacji sortowania czasu w Javie i dla Javy (Joshua Bloch jest również osobą, która wdrożyła w 1997 r. Zmodyfikowany scalak, który jest nadal używany w Javie, i można mieć nadzieję, że Java będzie w końcu przełącz się na swój ostatni port sortowania czasu).

Niektóre wyjaśnienia portu Java timsort jest tutaj , jest diff tutaj (z wskazówki dla wszystkich potrzebnych plików), plik klucza jest tutaj - FWIW, podczas gdy ja jestem lepszy niż C programista programista Java, w tym przypadku uważam, Kod Javy w Javie jest ogólnie bardziej czytelny niż kod Tima w C ;-).

Alex Martelli
źródło

@Chris, „Przeglądaj źródła Pythona” to skrót we wszystkich paskach zakładek mojej przeglądarki - wskazuje na svn.python.org/view/python/trunk ;-).

Alex Martelli

Chcę wiedzieć, co list_ass_item()robi ta funkcja . :)

Chris Lutz

Wykonuje przypisanie do elementu listy (tak jak przypisanie elementu list_ass_slice do wycinka listy), nie ma nic wspólnego z sortowaniem. Wydaje mi się, że skrót „przypisanie” sprawia, że nazwa jest śmieszna ...

Alex Martelli

Aktualna wersja z listsort.txtdodaje kilka zauważa, że adres wspólnych nieporozumień.

Tim Peters,

Chciałem tylko dostarczyć bardzo pomocny link, którego przegapiłem w wyczerpującej odpowiedzi Alexa: ogólne wyjaśnienie sortowania czasu w Pythonie (z wizualizacjami wykresów!).

(Tak, algorytm jest teraz zasadniczo znany jako Timsort )

u0b34a0f6ae
źródło

We wczesnych wersjach Pythona funkcja sort zaimplementowała zmodyfikowaną wersję quicksort. Jednak został uznany za niestabilny i od wersji 2.3 przeszli na używanie adaptacyjnego algorytmu scalania.

Silfverstrom
źródło

quicksort nie jest „uważany za niestabilny” - zgodnie z powszechnie używanymi definicjami quicksort jest niestabilny - to znaczy, że pierwotna kolejność dwóch obiektów nie jest zachowywana, jeśli są one równe podczas tego rodzaju. Niestabilny algorytm sortowania oznacza, że musisz wymyślić wszelkiego rodzaju `` magię '', aby rozsądnie sortować dane według wielu kryteriów, zamiast po prostu móc po prostu łańcuchowo sortować połączenia - w sortowaniu czasu, jeśli chcesz sortować według DOB, a następnie nazwać , najpierw sortuj według nazwy, a następnie DOB Nie możesz tego zrobić za pomocą quicksort

Tony Suffolk 66