팀소트
(팀 정렬에서 넘어옴)
| 분류 | 정렬 알고리즘 |
|---|---|
| 자료 구조 | 배열 |
| 최악 시간복잡도 | [1][2] |
| 최선 시간복잡도 | [3] |
| 평균 시간복잡도 | |
| 공간복잡도 |
팀소트(Timsort)는 수많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 안정 정렬 알고리즘의 하나이다. 합병 정렬과 삽입 정렬이 기원이다. 2002년 파이썬 프로그래밍에 사용하기 위해 팀 피터스가 구현했다.
팀소트는 버전 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