정렬 알고리즘 자체보다는 정렬 함수의 기능과 관련 내용을 간단히 다룬다.
sorted()
sorted() 함수는 리스트뿐만 아니라 문자도 정렬이 가능하다.
>>> a = [2, 5, 1, 9, 7]
>>> sorted(a)
[1, 2, 5, 7, 9]
>>> b = 'zbdaf'
>>> sorted(b)
['a', 'b', 'd', 'f', 'z']
>>> ''.join(sorted(b))
'abdfz'리스트를 결과로 리턴하기 때문에, 다시 문자열로 결합하기 위해 join()을 이용할 수 있다.
list.sort()
sorted()라는 별도 함수 외에도 리스트 자료형은 sort() 메소드를 제공하며, 리스트 자체를 정렬할 수 있다.
이를 제자리 정렬(In-place Sort)이라고 부르는데, 일반적으로 제자리 정렬 알고리즘은 입력을 출력으로 덮어 쓰기 때문에 별도의 추가 공간이 필요하지 않으며, 리턴값이 없다.
alist.sort() # sort()는 리스트 자체를 제자리 정렬
alist = blist.sort() # 잘못된 구문, sort() 함수는 None을 리턴하므로 주의key function
sorted() 함수와 sort() 메소드는 key= 옵션을 지정해 정렬을 위한 키 함수를 별도로 지정할 수 있다.
다음 코드는 정렬을 위한 함수로 길이를 구하는 len을 지정한 경우다.
>>> c = ['ccc', 'aaaa', 'd', 'bb']
>>> sorted(c, key=len)
['d', 'bb', 'ccc', 'aaaa']다음은 함수를 이용해 첫 문자열(s[0])과 마지막 문자열(s[-1]) 순으로 정렬하도록 지정했다.
>>> a = ['cde', 'cfc', 'abc']
>>> def fn(s):
... return s[0], s[-1]
...
>>> sorted(a, key=fn)
['abc', 'cfc', 'cde']
>>> sorted(a, key=lambda s: (s[0], s[-1]))
['abc', 'cfc', 'cde']정렬 알고리즘과 팀소트
파이썬의 정렬은 팀소트(Timsort)를 사용한다.
팀소트는 ‘실제 데이터는 대부분 이미 정렬되어 있을 것이다’라고 가정하고
실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘으로,
단일 알고리즘이 아니라 삽입 정렬과 병합 정렬을 적절히 조합한 알고리즘이다.
코딩 테스트에서 별다른 제약사항이 없는 한,
대부분의 경우 정렬이 필요할 때는 파이썬의 정렬 함수를 사용하는 편이 가장 빠르다.
팀소트를 사용하면서도, 내장 함수로서 저수준의 언어를 이용해 작성되었기 때문이다.
| 알고리즘 | 최선 | 평균 | 최악 |
|---|---|---|---|
| 퀵 정렬 | Ω(n log n) | Θ(n log n) | O(n^2) |
| 병합 정렬 | Ω(n log n) | Θ(n log n) | O(n log n) |
| 팀소트 | Ω(n) | Θ(n log n) | O(n log n) |
표와 같이 시간 복잡도로 비교해보면 장점이 더욱 돋보인다.
퀵 정렬은 빠른 알고리즘이긴 하지만 최악의 경우 O(n^2)이 될 수 있다.
병합 정렬은 항상 일정한 속도를 보이지만 O(n log n) 이상 빠르게 처리할 수 없다.
다른 정렬 알고리즘은 최선일 때도 Ω(n log n)에 머무르는 데 반해,
팀소트는 ‘실제 데이터는 대부분 이미 정렬되어 있을 것이다’를 가정하고 최적화를 한다.
이론적으로 어떠한 정렬 알고리즘도 한 번 이상 비교하게 되면 Ω(n log n)보다 빨라질 수 없지만,
팀소트는 이미 정렬되어 있는 경우 비교를 건너뛰기 때문에 Ω(n)까지 가능하다.
출처:
- 박상길. 파이썬 알고리즘 인터뷰 - 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트.
- Sorting HOW TO
