정렬

Python sort 와 key

실전에서는 이 한 줄이면 된다

카드 여섯 장을 점수가 높은 사람부터, 점수가 같으면 이름순으로 세웁니다. 먼저 맞혀 보세요. 이름순으로 한 번 줄을 세운 뒤 점수 높은 순으로 줄을 세우면 80점인 세 사람은 어떤 순서로 설까요?

kim80점

lee90점

amy80점

bob70점

tom90점

zed80점

목표 순서 · lee · tom · amy · kim · zed · bob

누른 횟수 0

기준을 0번 적용해서 만들었습니다. 가장 적게는 2번입니다. 이름순을 먼저, 점수순을 나중에 합니다.

기준을 묶어 한 줄로 — sorted(cards, key=lambda c: (-c[1], c[0]))
key — 카드마다 정렬용 값을 한 번씩 만들어 그 값으로 줄 세우는 함수. lambda c: … 는 카드 c 를 받아 값을 돌려주는 이름 없는 한 줄 함수
같은 값은 원래 순서를 지킨다 = 안정 정렬. 이름순이 점수순 뒤에도 살아남은 이유

이 정렬 도구가 sorted 입니다. 리스트에는 같은 일을 제자리에서 하는 sort() 도 있습니다.

방향이 다른 기준은 부호로 맞춘다

점수는 높은 순, 이름은 abc순 — 방향이 서로 다르다. 점수의 부호를 바꾸면 높은 점수가 작은 값이 되어 앞에 선다
reverse=True 는 key 전체를 뒤집는다 — 이름까지 거꾸로 선다. 80점끼리 zed → kim → amy
문자열에는 부호가 없다 — -'kim' 은 TypeError. 이름만 거꾸로 하고 싶으면 이름을 거꾸로 먼저 정렬하고 점수순을 나중에 정렬한다

코드는 key 를 만들고, key 로 줄 세운다

sorted(key=…) 가 안에서 하는 일을 풀어 쓴 코드입니다. 줄 세우는 알고리즘은 앞 장에서 본 정렬들과 비슷한 방법이고 여기서는 보이지 않습니다. ①과 같은 카드 여섯 장으로 다음을 눌러 key 가 한 장씩 만들어지는 걸 보세요.

카드마다 정렬용 key 를 만들어 두고, key 가 작은 순서로 줄 세웁니다

이름	점수	key	순서
kim	80	·	·
lee	90	·	·
amy	80	·	·
bob	70	·	·
tom	90	·	·
zed	80	·	·

다음을 눌러 한 줄씩 넘겨 보세요

keyed = 0

by_key.py

1def by_key(cards):
2 keyed = []
3 for name, score in cards:
4 key = (-score, name)
5 keyed.append((key, name, score))
6 keyed.sort()
7 return [(n, s) for k, n, s in keyed]

0 / 22

key = (-score, name) — 점수는 부호를 바꿔 첫째 값에, 이름은 둘째 값에 둔다
keyed.sort() — 튜플은 첫째 값부터 견주고, 같으면 다음 값을 본다
끝나면 — lee 와 tom(90점)이 앞, 80점 amy·kim·zed, 마지막이 bob(70점)

점수만 보고 낮은 순으로 한 번 정렬합니다. sorted(cards, key=lambda c: c[1]). 원래 줄은 kim → lee → amy → bob → tom → zed 입니다. 80점 세 사람은 어떤 순서로 설까요?

sort() 와 문자열 숫자에서 틀린다

a = a.sort() — sort() 는 제자리에서 정렬하고 None 을 돌려준다. 이렇게 쓰면 a 가 None 이 된다. 새 리스트가 필요하면 sorted(a)
숫자 모양 문자열 — sorted(['10', '9', '2']) 는 ['10', '2', '9']. 글자 순서로 견주기 때문이다. key=int 를 주면 ['2', '9', '10']
숫자와 문자열을 섞으면 — sorted([3, 'a']) 는 TypeError. 견줄 수 없는 두 값이 만나서다
정렬이 느리지 않다 — 이 컴퓨터에서 10만 장을 key 로 정렬하는 데 약 0.03초였다. 컴퓨터마다 다르다

문제에서 이 말이 보이면

여러 기준으로 정렬정렬 기준을 직접 정한다N log N 이면 충분한 정렬

원리를 보려고 직접 짠 앞의 정렬들과 달리 실전에서는 sorted() 한 줄이면 됩니다. 파이썬의 정렬은 병합 정렬과 삽입 정렬을 섞은 방식(Timsort)이라 N log N 입니다. 이미 정렬된 입력에는 훨씬 빠릅니다 — 이 컴퓨터에서 정렬된 10만 개가 약 0.0003초였습니다.

다음 장에서는 앞에서부터 하나씩 찾는 선형 탐색을 봅니다.