728x90
정렬 알고리즘 중에서 가장 인기 있는 알고리즘은 존 논 포이만(John von Neumann) 이 설계한 병합 정렬(Merge Sort) 이다. 대부분은 퀵 정렬이 빠르지만 데이터에 따라 편차가 큰 반면, 병합 정렬은 일정하게 O(n log n) 의 안정적인 성능을 보이며, 무엇보다 안정 정렬(Stable Sort) 라는 점에서 많이 선호되는 편이다.
파이썬의 정렬은 팀소트(Timsort) 를 사용한다. 팀소트는 팀 피터스(Tim Peters) 가 피터 매킬로이(Peter Mcllroy) 의 1993년 논문을 기반으로 2002년도에 파이썬을 위해 C로 구현한 알고리즘으로, 창안자인 팀 피터스의 이름을 따 팀소트로 불린다.
팀소트는 애초에 학계에서 받아들여질 만한 우아한 알고리즘을 목표로 하기보다는, '실제 데이터는 대부분 이미 정렬되어 있을 것이다' 라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘이다. 데이터가 엉망으로 뒤죽박죽 섞여 있는 일은 실제로는 거의 일어나지 않을 것이라고 가정한 셈이다.
팀소트는 개별적인 단일 알고리즘이 아니라 삽입 정렬과 병합 정렬을 휴리스틱하게 적절히 조합해 사용하는 정렬 알고리즘이다.
▷ 정렬 알고리즘별 시간 복잡도
| 알고리즘 | 최선 | 평균 | 최악 |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n2) |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) |
| 팀소트 | O(n) | O(n log n) | O(n log n) |
(출처: 파이썬 알고리즘 인터뷰)
728x90
'개발새발 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 시스템 설계 인터뷰 전에 알아둬야 할 알고리즘 (0) | 2022.08.18 |
|---|