TIL#26-1 PYTHON 기초 (15)

여러가지 정렬방법

sorted() 함수

a = [4, 1, 8, 3, 9]
print(sorted(a))
-> [1, 3, 4, 8, 9]

b = 'fjsao'
print(sorted(b)) # 알파벳 순서대로 정렬한 리스트로 출력
-> ['a', 'f', 'j', 'o', 's']
print(''.join(sorted(b))) # 리스트를 문자열로 출력
-> afjos

❗️ 리스트 자료형은 sort() 메소드 제공. 리스트 자체를 정렬.
입력을 출력으로 덮어 쓰기 때문에 별도의 추가공간이 필요하지 않고, 리턴값이 없다.

sorted() -> 정렬 결과를 별도로 리턴
sort() -> 제자리정렬. None 리턴

⭐️ sorted()는 key=옵션 을 지정해 정렬을 위한 키 또는 함수를 별도 지정할 수 있다.

c = ['ccc', 'aaaaa', 'd', 'bb']
print(sorted(c, key=len))  # key=옵션 지정가능. 길이순서대로 정렬.
-> ['d', 'bb', 'ccc', 'aaaaa']

d = ['cde', 'cfc', 'abc']

def fn(s):
    return s[0], s[-1]

print(sorted(d))
-> ['abc', 'cde', 'cfc']
print(sorted(d, key=fn)) # 두번째 키값을 s[-1]로 비교하게 하는 함수 이용.
-> ['abc', 'cfc', 'cde']

# 람다 함수를 이용해도 가능

print(sorted(d, key=lambda s:(s[0], s[-1])))
-> ['abc', 'cfc', 'cde']

팀소트

정렬 알고리즘 중에서 가장 인기있는 알고리즘은 병합정렬Merge Sort이다. 대부분 퀵정렬이 더 빠르지만 데이터에 따라 편차가 큰 반면, 병합정렬은 일정하게 O(n log n)의 안정적인 성능을 보인다.

파이썬의 정렬은 팀소트Timsort를 사용한다. 팀 피터스(Tim Peters)라는 사람이 피터 매킬로이(Peter Mcllroy)의 1993년 논문을 기반으로 2002년도에 파이썬을 위해 C로 구현한 알고리즘이다. '실제 데이터는 대부분 이미 정렬되어 있을 것이다'라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘이다. 개별적인 단일 알고리즘이 아니라 삽입정렬과 병합정렬을 적절히 조합해 사용하는 정렬 알고리즘이다.

⭐️ 정렬 알고리즘별 시간 복잡도

알고리즘	최선	평균	최악
퀵 정렬	Ω(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) 이상 빠르게 처리 못함.