팀소트 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
| class      = [[정렬 알고리즘]]
| image      =
| caption    = 
| data       = [[배열]]
| time       = <math>O(n\log n)</math><ref>{{웹 인용|title=[Python-Dev] Sorting |url=http://mail.python.org/pipermail/python-dev/2002-July/026837.html |last=Peters |first=Tim |work=Python Developers Mailinglist |access-date=24 February 2011 |quote=[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).}}</ref><ref>{{서적 인용|title=[DROPS]|year=2018 |doi=10.4230/LIPIcs.ESA.2018.4 |url=http://drops.dagstuhl.de/opus/volltexte/2018/9467/ |access-date=1 September 2018 |quote=TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.|last1=Auger |first1=Nicolas |last2=Jugé |first2=Vincent |last3=Nicaud |first3=Cyril |last4=Pivoteau |first4=Carine |isbn=9783959770811 |s2cid=44091254 }}</ref>
|best-time=<math>O(n)</math><ref name="Chandramouli">{{콘퍼런스 인용|last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014}}</ref>
|average-time=<math>O(n\log n)</math>
|space=<math>O(n)</math>
|optimal=예
}}
'''팀소트'''(Timsort)는 수많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 [[:분류:안정 정렬|안정]] [[정렬 알고리즘]]의 하나이다. [[합병 정렬]]과 [[삽입 정렬]]이 기원이다. 2002년 [[파이썬]] 프로그래밍에 사용하기 위해 [[팀 피터스]]가 구현했다.

팀소트는 버전 2.3부터 파이썬의 표준 정렬 알고리즘이다. 자바 SE 7, 안드로이드, [[GNU 옥타브]], [[V8 (자바스크립트 엔진)|V8]], [[스위프트 (프로그래밍 언어)|스위프트]], [[러스트 (프로그래밍 언어)|러스트]]에서 프리미티브가 아닌 타입의 배열을 정렬하기 위해서도 사용된다.

피터 매클로이의 1993년 논문 "최적의 정렬 및 정보이론복잡성"(Optimistic Sorting and Information Theoretic Complexity)의 기법들을 사용한다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* [http://bugs.python.org/file4451/timsort.txt timsort.txt] – original explanation by Tim Peters

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:비교 정렬]]
[[분류:안정 정렬]]