자료구조 정렬 비교 (Tim sort, Tree sort)

Tim sort

이 알고리즘은 기존의 insert sort(삽입정렬)와 merge sort(병합정렬) 알고리즘을 둘다 사용하여 좀더 빠르게 작동하는 알고리즘이다.

 

아래의 도표를 예시로 진행 순서를 설명하면,

 

1. 적당히 Increase chunk와 Decrease chunk로 자른다.
2. 각 조각들을 insert sort를 사용해 정렬한다. (다음 단계로 넘어 가기 전, Decrease chunk는 내림차순이므로 뒤집어준다.)
3. 조각들을 merge sort로 정렬하며 병합해준다.

 

Tim sort는 배열이 완전 무작위가 아닌 어느정도는 순서에 맞게 정렬되어있다는 컨셉에서 착안한 방식이다. 아래의 예시에서는 3, 10 29 와 7,5 배열이 이미 순서대로 배열되어 있다.

그 결과, 시간복잡도는 맨 아래의 도표와 같이 효율적으로 계산된다. 현재 java, python, rust등 다양한 프로그래밍 언어에서 기본 정렬 알고리즘으로 채택하여 사용하고 있다.

   

Tim sort 정렬과정

 

Tree sort

tree sort 알고리즘은 tree 구조의 이점을 활용하여 개발된 정렬방식으로 Binary search tree에 기반한다. Binary search tree란 상위노드인 부모노드를 기준으로 작은 값이면 왼쪽에, 큰값이면 오른쪽에 배치하는 구조이다.

 

검색속도가 빠르다는 장점이있는 자료구조로, 해당 구조는 아래와 같은 형태로 데이터를 저장하며, 아래쪽으로 자식노드를 생성하며 정렬을 진행하는 방식이다.

 

아래의 예시로 순서를 설명하면,

 

1. 맨 첫번째 숫자부터 진행이 되는데 10을 기준노드로 하여, 3은 10보다 작으므로 왼쪽에 배치한다.
2. 그 다음 숫자 29는 10보다 크므로 오른쪽에 배치한다.
3. 2는 3보다 작으므로 왼쪽에 배치한다.
4. 7은3보다 크므로 오른쪽에 배치한다.
5. 5는 7보다 작으므로 7 왼쪽에 배치한다.
6. 21은 29보다 작으므로 왼쪽에 배치한다.

 

Tree 구조 및 정렬방식

 

각 정렬방식은 아래의 시간복잡도를 가진다.

 

시간 복잡도 비교