정렬

퀵 정렬

기준 하나로 좌우를 가르기

카드 일곱 장이 있습니다. 맨 앞 카드를 기준으로 삼고 나머지를 한 장씩 보며 왼쪽과 오른쪽 묶음으로 가릅니다.

기준이 가운데쯤에 놓여야 빠르다

• 반씩 갈리면 — 층이 log N 개다. 층마다 카드를 한 번씩 보니 N log N
• 한쪽으로 쏠리면 — 한 번에 기준 카드 하나만 정해진다. 층이 N 개가 되어 비교가 N(N−1)/2, 곧 N²
• 정렬된 카드 — 위의 「이미 정렬된 카드로 해 보기」에서 왼쪽이 0장이었다. 일곱 장이면 비교 21번이다(손으로 해 본 카드는 13번). 10만 장이면 4,999,950,000번으로 8분 걸린다

코드는 가르고 양쪽에 되풀이하는 것이 전부다

① 에서 한 순서 그대로 기준을 맨 앞 칸에 두고 앞에서부터 훑습니다. 다음을 눌러 첫 분할을 한 줄씩 보세요. 안쪽 분할은 기준을 놓은 줄 하나로 묶어 보여 줍니다.

• lo · hi — 지금 가르는 구간. 처음엔 0번 칸부터 6번 칸까지다
• i — 작은 카드 묶음의 끝 칸 번호
• j — 지금 기준과 견주는 칸. lo + 1 부터 hi 까지 간다

퀵 정렬에서 틀리는 자리

• 정렬된 큰 입력 — 5000장만 돼도 RecursionError: maximum recursion depth exceeded 가 난다. 층이 N 개가 되는데 파이썬의 기본 재귀 한도는 1000이다
• 같은 값이 많으면 — 5000장이 모두 같아도 같은 에러가 난다. 같은 카드는 < 가 거짓이라 전부 오른쪽으로 가서 쏠린다
• 기준을 가운데나 무작위로 — 가운데 카드를 맨 앞으로 옮겨 기준으로 삼으면 정렬된 5000장도 끝까지 간다
• 같은 값의 순서가 뒤집힌다 — 2a 1b 1c 를 정렬하면 1c 1b 2a 가 된다. 안정 정렬이 아니다
• 리스트 컴프리헨션 버전 — 짧게 쓸 수 있지만 가를 때마다 새 리스트를 만들어 메모리를 더 쓴다

코딩테스트에서 이 말이 보이면

실전에서 정렬이 필요하면 sorted() 한 줄이면 됩니다.

다음 장에서는 여러 기준으로 정렬하는 Python sort 와 key 를 봅니다.