Tim Sort1 Tim Sort -목차- 1. Tim sort의 등장 2. Tim sort의 기본 원리 3. Tim sort의 최적화 기법 3.1 Run 3.2 Binary Insertion Sort 3.3 Merge 4. Galloping 참고 자료 1. Tim sort의 등장 2002년 소프트웨어 엔지니어 Tim Peters에 의하여 Tim sort가 등장했다. 이 정렬 알고리즘은 Insertion sort와 Merge sort를 결합하여 만든 정렬이다. 실생활 데이터의 특성을 고려하여 더욱 빠르게 고안된 이 알고리즘은 최선의 시간 복잡도는 \(O(n)\), 평균은 \(O(n\log n)\), 최악의 경우 시간 복잡도는 \(O(n\log n)\)이다. Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 .. 2022. 2. 17. 이전 1 다음
