[내일배움캠프 33일차 TIL] python 정렬 - timsort

 

 

 

잘 알려진 정렬 알고리즘은 다음과 같은 종류가 있다

 

시간복잡도가 O(n^2)인 bubble sort와 Insert sort를 제외하면 Heap sort, Merge sort, Quick sort를 사용하는 것이 좋을 것이다.

모든 정렬 알고리즘은 장단점이 있어 어떤 한 정렬이 탁월하게 좋다고 선택할 수는 없지만 추가 메모리를 많이 사용하지 않고, 최악의 경우에도 O(nlogn)으로 동작하는 정렬 알고리즘이 필요했다

 

 

 

Tim Sort

Tim sort는 소프트웨어 엔지니어인 Tim Peters에 의해 등장하였다. 이 정렬 알고리즘은 Insertion sort(삽입정렬)와 Merge sort(합병 정렬)를 결합하여 만든 정렬이다

최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우는 O(nlogn)이다. Tim sort는 두 정렬 방법을 결합하여 안정적이며, 추가 메모리는 사용하지만 기존의 합병정렬에 비해 적은 추가 메모리를 사용하여 다른 O(nlogn)의 시간 복잡도를 가지는 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.

 

 

Tim sort는 인접한 메모리와의 비교를 반복하여 참조 지역성의 원리를 잘 만족한다고 할 수 있다. 전체를 작은 덩어리로 잘라 각각의 덩어리를 삽입정렬로 정렬한 뒤 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어이다.

Tim sort에 관해 기술적으로 자세하게 다룬 내용은 이 블로그로!

참조지역성
기억 장치 내의 정보를 균일하게 접근하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성이다. 컴퓨터 프로그램이 일정 기간 동안 특정한 메모리 위치 집합에 접근하려는 경향이 있는 현상으로 쉽게 말해 주소가 서로 가까운 명령어에 접근하는 경향을 나타낸다