팀 정렬 (Tim Sort) + ArrayList

• 팀 정렬(Tim Sort)

 우리가 아는 O(NlogN)의 시간복잡도를 갖는 힙 정렬, 병합 정렬, 퀵 정렬들은 같은 시간복잡도를 같지만 상황에 따라 다른 속도를 보여준다. 시간 복잡도는 실제로 C×nlogn+α 이고 상대적으로 무시할 수 있는 부분인 α를 제외하고 C에 따라 속도가 달라질 수 있다. 여기서 C는 지역성에 따라 달라지는 값으로 지역성이 좋으면 메모리를 참조할때 cache hit가 자주 발생해 속도가 빨라져 속도가 빨라지므로 이 부분이 C에 영향을 준다. 

 힙 정렬은 퀵 정렬에 비해 지역성이 떨어지고 불필요한 교환이 많아 보통 퀵 정렬보다 느리고 퀵 정렬은 빠른 정렬 방법이지만 최악의 경우 O(N^2)의 시간복잡도를 갖기 때문에 늘 좋은 정렬 방법은 아니다. 마지막으로 병합 정렬은 퀵 정렬에 비해 비교 횟수가 적지만 Buffer를 생성해 정렬을 하기 때문에 메모리 접근이 분산될 수 밖에 없으며 이동 횟수도 많다는 단점이 있다.

 이렇게 각각의 단점들이 존재하기 때문에 데이터드르이 종류와 상관없이 최적으로 정렬을 잘 수행하기 위해 개발한 정렬 방법이 팀 정렬이다.

 팀 정렬은 병합 정렬과 삽입 정렬을 적절히 섞어놓은 정렬이다. 자바에서 퀵 정렬이 Arrays.sort로 구현되어있는 것과 같이 (Dual-Pivot QuickSort로 사실 보통의 QuickSort보다 빠르다) 팀 정렬은 Collections.sort로 구현되어 있다. 최선의 시간 복잡도는 O(n)이고 평균, 최악은 O(nlogn)이다. 그리고 안정적인 정렬이다.

 실제 팀 정렬이 진행되는 과정을 살펴보자. 대략적으로 말하면 우선 배열을 여러개의 run으로 나눠준다. 여기서 run이란 것은 쉽게 말해서 배열의 길이와 효율에 따라 정해진 최솟값이상의 요소를 갖는 집단이고 병합 정렬에서 배열을 잘게 나눈 것과 같다고 생각하면 된다.(이때 run안에 요소의 개수가 최솟값을 넘더라도 다음 요소를 추가하는 것이 더 효율적이라 판단이 되면 run은 계속 커질 수 있다) 배열을 여러개의 run으로 나눴으면 이제 각각의 run안에서 삽입정렬을 진행하는데 이진탐색을 이용하여 더 효율적으로 정렬한다. 그리고 삽입정렬로 정렬된 run들을 병합정렬을 이용하여 1개의 배열로 정렬을 완료하면 정렬이 종료된다.

 팀 정렬을 사용할 때는 일반적인 배열을 쓸 수 없고 ArrayList를 이용해야한다. ArrayList는 Array와 크기가 동적이며 Object element만 담을 수 있어서 primitive type인 int, byte, char등을 담기 위해서는 Wrapper Class(Byte, Character, Integer 등)를 사용해야 한다. ArrayList에 값을 넣으려면 Array와 달리 ArrayList의 add(index, value)함수를 써야하고 index를 입력하지 않으면 자동으로 맨 끝에 값이 추가된다. 삭제하려면 remove(index)를 이용하고 크기는 size()함수, 값 출력은 .get(index)함수를 이용하면 된다. 마지막으로 값을 검색하려면 contains(value)를 이용해 true, false를 반환받을 수 있고 

index를 반환받으려면 indexOf(value)를 이용해야하며 검색 실패시 -1을 반환받는다.

---

reference 

 - https://d2.naver.com/helloworld/0315536

 - https://zorba91.tistory.com/287