Какой алгоритм использует встроенный sort()
метод в Python? Можно ли посмотреть код этого метода?
python
algorithm
sorting
python-internals
Йоханнес
источник
источник
sort()
метод или каково форматирование интерпретатора, но он должен быть где-то там, и я уверен, что он реализован на C из соображений скорости.Ответы:
Конечно! Код здесь , начинается с функции
islt
и продолжается некоторое время ;-). Как следует из комментария Криса, это код C. Вы также захотите прочитать этот текстовый файл для текстового объяснения, результатов и т. Д.Если вы предпочитаете читать Java-код, а не C-код, вы можете взглянуть на реализацию Timsort Джошуа Блоха в Java и для Java (Джошуа также разработал в 1997 году модифицированную сортировку слиянием, которая все еще используется в Java, и можно надеяться, что Java будет со временем переключаюсь на свой недавний порт тимсорт).
Некоторое объяснение Java-порта timsort здесь , diff здесь (с указателями на все необходимые файлы), ключевой файл здесь - FWIW, хотя я лучше программист на C, чем Java-программист, в этом случае я нахожу Java-код Джошуа в целом более читабелен, чем код Тима на C ;-).
источник
list_ass_item()
делает эта функция . :)listsort.txt
добавляет некоторые примечания , что адрес общего замешательства.Я просто хотел предоставить очень полезную ссылку, которую я пропустил в исчерпывающем ответе Алекса: высокоуровневое объяснение временной сортировки Python (с визуализацией графиков!).
(Да, сейчас алгоритм известен как Timsort )
источник
В ранних версиях python функция сортировки реализовывала модифицированную версию быстрой сортировки. Однако это было сочтено нестабильным, и с 2.3 они перешли на использование алгоритма адаптивной сортировки слиянием.
источник