정렬

언제 쓰나

문제에 이런 신호가 보이면 정렬부터 떠올린다.

“크기 순으로”, “사전순으로”, “K번째 수” — 정렬 자체가 답
“가장 가까운 쌍”, “겹치는 구간” — 정렬해두면 이웃끼리만 비교하면 됨
그리디, 이분 탐색, 투포인터의 전처리 — 이 기법들은 대부분 정렬된 입력을 전제로 한다

핵심 아이디어

기본 정렬 세 가지는 “정렬된 구간을 어떻게 넓혀가는가”가 다르다.

버블: 인접한 쌍을 계속 교환 — 큰 값이 뒤로 떠오른다
  [5 3 8 4] → [3 5 4 8] → [3 4 5 8]
                     ↑ 한 바퀴마다 맨 뒤 확정
 
선택: 남은 구간의 최솟값을 찾아 앞으로
  [5 3 8 4] → [3|5 8 4] → [3 4|8 5] → [3 4 5|8]
               ↑ 한 바퀴마다 맨 앞 확정
 
삽입: 현재 값을 정렬된 왼쪽 구간의 제자리에 끼워 넣기
  [3 5|8 4] → 4를 왼쪽으로 → [3 4 5 8]

셋 다 O(n²)이라 실전에서 직접 쓸 일은 거의 없지만, 배열을 순회하고 비교하고 교환하는 기본 감각을 익히기에 좋다.

코드 템플릿

학습용 삽입 정렬은 이렇게 생겼다.

def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums

실전에서는 내장 정렬을 쓴다. 파이썬의 sort()는 팀소트로 O(n log n)이 보장되고, 안정 정렬이라 같은 키의 원래 순서가 유지된다. 문제 조건은 key로 옮긴다.

arr.sort()                                  # 오름차순
arr.sort(reverse=True)                      # 내림차순
words.sort(key=lambda w: (len(w), w))       # 길이 순, 같으면 사전순
students.sort(key=lambda s: (-s[1], s[0]))  # 점수 내림차순, 이름 오름차순

“조건 A 순, 같으면 조건 B 순”이라는 문장은 그대로 튜플 (A, B)가 된다. 내림차순이 섞이면 숫자는 부호를 뒤집고, 문자열처럼 부호를 못 쓰는 타입은 reverse=True와 조합한다.

풀이 과정 따라가기

삽입 정렬이 [5, 3, 8, 4]를 정렬하는 과정이다. 왼쪽의 정렬된 구간이 한 칸씩 자란다.

함정

비교 함수 안에서 무거운 계산을 하지 않는다. key는 원소마다 한 번씩만 불리지만, 그 안에서 O(n) 연산을 하면 전체가 O(n² log n)이 된다.
문자열 숫자 정렬. ["10", "9", "1"]을 그대로 정렬하면 사전순으로 ["1", "10", "9"]가 된다. 숫자 기준이면 key=int.
안정성이 필요한 문제. “먼저 입력된 순서 유지” 조건은 파이썬 내장 정렬이 공짜로 보장하지만, 언어를 옮기면(예: C++ sort) 깨질 수 있는 전제다.