[Python]파이썬 정렬 알고리즘, Timsort

파이썬은 sort(), sorted() 메서드를 통해 정말 간편하게 정렬된 값을 얻을 수 있습니다.

사용하는 방법도 매우 쉽기에 내부 동작 원리에 대해서는 깊게 생각해본 적이 없었습니다. 이번 포스팅에서는 파이썬이 어떤 정렬 알고리즘을 사용하는지 알아보도록 하겠습니다.

 

Timsort

파이썬은 Tim sort라는 정렬 알고리즘 표준으로 채택되어 사용 중입니다. Timsort는 삽입정렬과 병합정렬을 합친 알고리즘입니다.

2001년도에 고안되었으며, 창시자인 Tim Peters의 이름을 따왔습니다. 또한, 이 알고리즘은 파이썬 뿐만 아니라 Java SE7, Android, 구글 크롬 엔진등 다양한 곳에서 채택되어 사용중입니다.

 

Timsort 특징

현실 세계의 데이터들은 완전 무작위가 아니라 어느정도는 정렬이 되어있는 경우가 많다는 것에서 착안한 알고리즘입니다.

Timsort는 이런 다양한 종류의 실제 데이터에서 잘 수행되도록 설계된 알고리즘이고, 삽입 정렬과 병합정렬을 합친 형태로 구현되었습니다.

 

최적의 시간 복잡도는 O(n), 평균 복잡도는 O(n log n), 최악의 경우는 O(n log n) 입니다.

 

알고리즘 원리

간단하게 수행 방법을 살펴보도록 하겠습니다. (대략적인 설명이므로 틀린 부분이 있을 수 있습니다.)

1. 먼저 정렬 대상이되는 전체 배열을 (보통) 2^5, 2^6 개의 덩어리로 나눕니다.
2. 각각의 덩어리들은 Insertion sort를 진행합니다.
   (삽입 정렬의 평균 복잡도는 O(n^2) 이지만, n의 크기가 적당히 작은 규모일때는 퀵정렬보다 빠른 속도를 보여줍니다.)
3. 그 후, 덩어리들을 합치면서 Merge sort를 진행합니다.
4. 정렬된 결과를 얻을 수 있습니다.

해당 포스팅에서는 알고리즘의 자세한 동작원리에 대해서는 다루지 않습니다. 따라서, 동작 원리가 자세하게 설명된 곳의 레퍼런스를 대체하도록 하겠습니다.

 

Tim Sort 동작법 - Youtube

 

일반적으로 프로그래밍 언어들의 내부 정렬 알고리즘을 꼭 알아야 할 이유는 없습니다. 다만, 해당 언어의 구현 원리에 대해 관심을 갖게 되다보면 한 번쯤은 의문점이 생길 것입니다. 그 시점에 공부해도 괜찮다고 생각합니다.

 

읽어주셔서 감사합니다 :)