Tim Sort (Incomplete)
참고 및 출처
새로운 정렬 알고리즘의 필요성
많은 정렬 알고리즘 중 시간복잡도가 O(nlogn)인 알고리즘이 있음.
이 중 각각 장단점이 있어서 어느 하나의 정렬 알고리즘이 월등히 좋다고 할 수가 없었음.
따라서 메모리도 적게 사용하고 최악의 경우에도 시간복잡도가 O(nlogn)인 알고리즘이 필요했음.
Tim Sort란
파이썬에서 사용되고 있는 정렬 알고리즘은 무엇인지 궁금해서 검색해보니 Tim sort라고 나옴.
이 정렬 알고리즘은 Insertion sort와 Merge sort를 결합하여 만든 정렬임.
최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는 O(nlogn).
Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘임.
현재 2.3 이후 버전의 Python, Java SE 7, Android, Google chrome (V8), swift까지 많은 프로그래밍 언어에서 표준 정렬 알고리즘으로 채택되어 사용되고 있음.
Tim Sort 원리
정리하면 작은 배열에 대해선 삽입 정렬이 퀵정렬보다 빠르다는 것이 요점임.
이것을 이용하여 전체를 작은 덩어리로 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어라는 것.
- Insertion sort란?
- gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
Tim Sort 최적화 기법
이 알고리즘에서 사용한 Insertion Sort는 Binary Insertion Sort임.
Code
1
This post is licensed under CC BY 4.0 by the author.