📌 파이썬의 정렬 목차

• sorted() vs. sort()
• 팀소트
• 파이썬의 정렬 함수가 가장 빠른 편

sorted() vs. sort()

sorted()

• 리스트 뿐만 아니라 문자열도 정렬이 가능하다.
• 반환 : 정렬된 리스트
  (리스트를 문자열로 복구하려면 "".join(lst))
• 추가 공간이 필요하다. 즉, 변수에 할당해야 한다.
• key나 함수를 지정하여 정렬할 수 있다.

# key로 정렬
alist = ['ccc','a','bb']
sorted(alist, key=len)
# ['a','bb','ccc']

# 함수로 정렬
1. 
def fn(s):
	return s[0], s[-1]
   
alist = ['abe', 'dce', 'abc'] 
sorted(alist, key=fn)
# ['abc', 'abe', 'dce']

2.
# 람다를 쓰면 1번을 한줄로 작성할 수 있다.
sorted(alist, key=lambda x: (x[0], x[-1]))

sort()

• 제자리 정렬 : 리스트 자체를 정렬 (입력을 출력으로 덮어씀)
• => 추가 공간이 필요없음.
• => 반환 : None
  alist = blist.sort() -> None 반환

팀소트(Tim Sort)

+) 병합 정렬 (Merge Sort)

• 가장 인기있는 정렬 알고리즘
• 병합 정렬은 일정하게 O(nlogn)의 안정적 성능을 가짐.
  (퀵 정렬은 데이터에 따라 편차가 큰 단점. (대부분 더 빠르지만 최대 O(n^2)))
• 안정 정렬(Stable Sort)라는 점이 장점.

Python의 sorted() = 팀소트

• '실제 데이터는 대부분 이미 정렬되어있을 것이다.'라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘.
• 이미 정렬된 경우 비교를 건너뛰기 때문에 오메가(n)까지 성능이 좋아짐.
  (퀵 소트, 병합 정렬은 최선이 O(nlogn))
• 단일 알고리즘이 아님. 삽입 정렬과 병합정렬을 휴리스틱하게 조합하여 사용.

파이썬의 정렬 함수가 가장 빠른 편

• 실제 데이터에 적합한 팀소트를 사용하고
• 내장 함수로서 저수준의 언어(Cpython -> C언어)로 작성되었기 때문이다.

=> 코테에선 정렬을 하려면 파이썬 내장 함수를 써라.