팀소트
팀소트(Timsort)는 수많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 안정 정렬 알고리즘의 하나이다. 합병 정렬과 삽입 정렬이 기원이다. 2002년 파이썬 프로그래밍에 사용하기 위해 팀 피터스가 구현했다.
| 분류 | 정렬 알고리즘 |
|---|---|
| 자료 구조 | 배열 |
| 최악 시간복잡도 | [1][2] |
| 최선 시간복잡도 | [3] |
| 평균 시간복잡도 | |
| 공간복잡도 |
팀소트는 버전 2.3부터 파이썬의 표준 정렬 알고리즘이다. 자바 SE 7, 안드로이드, GNU 옥타브, V8, 스위프트, 러스트에서 프리미티브가 아닌 타입의 배열을 정렬하기 위해서도 사용된다.
피터 매클로이의 1993년 논문 "최적의 정렬 및 정보이론복잡성"(Optimistic Sorting and Information Theoretic Complexity)의 기법들을 사용한다.
각주
편집- ↑ Peters, Tim. “[Python-Dev] Sorting”. 《Python Developers Mailinglist》. 2011년 2월 24일에 확인함.
[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best).
- ↑ Auger, Nicolas; Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). 《[DROPS]》. doi:10.4230/LIPIcs.ESA.2018.4. ISBN 9783959770811. S2CID 44091254. 2018년 9월 1일에 확인함.
TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.
- ↑ Chandramouli, Badrish; Goldstein, Jonathan (2014). 《Patience is a Virtue: Revisiting Merge and Sort on Modern Processors》. SIGMOD/PODS.
외부 링크
편집- timsort.txt – original explanation by Tim Peters