개요

지난 네 편이 파이썬 문법과 라이브러리를 훑는 이야기였다면, 이번엔 알고리즘 쪽으로 한 칸 내려간다. 정렬이다.

사실 정렬은 1년 반쯤 전에 이론 정리 - < 알고리즘 >에서 한 번 정리했었다. 그런데 이번에 정렬 강의안을 다시 보다가 그 글에 구멍이 꽤 많다는 걸 알았다..

  • 시간복잡도만 적어놨다. 정렬을 고르는 기준이 속도 하나뿐인 것처럼 써놨다
  • 카운팅 정렬과 기수 정렬이 아예 없다. 비교를 안 하는 정렬이 있다는 걸 그때는 몰랐다
  • 선택 정렬 예제에 버그가 있다. 안쪽 반복문에서 j++를 써야 하는데 i++를 썼다

그래서 이번 편에서 정렬 8종을 전부 파이썬으로 다시 옮기고, 속도 말고도 봐야 할 기준 세 가지를 앞에 깔았다. 그리고 마지막엔 결국 실무에서 쓰는 건 sorted() 한 줄이라는 얘기로 마무리한다. 여덟 개를 직접 짜보는 이유가 거기에 있기 때문이다.

정렬 알고리즘은 왜 이렇게 많은가? 빠르기가 전부라면 제일 빠른 하나만 남으면 될 텐데.

같은 여덟 개를 C++로 옮기고 직접 구현하며 삽질한 이야기는 C++ - < 1 >에 따로 적었다. ( 강의 자료는 대외비라 슬라이드를 그대로 싣지 않았다. 개념만 직접 다시 그렸다 )

정렬을 고르는 네 가지 축

정렬(sorting)은 2개 이상의 자료를 어떤 기준에 따라 작은 값부터 큰 값 순서로(오름차순), 혹은 그 반대로(내림차순) 다시 늘어놓는 것이다. 이때 순서를 정하는 기준이 되는 값을 키(key) 라고 부른다. 학생 명단을 성적순으로 세운다면 성적이 키다. sorted(students, key=…)의 그 key가 정확히 이 단어다.

예전 글에서는 각 정렬마다 시간복잡도만 적어두고 끝냈다. 그런데 실제로 정렬을 고를 때 보는 건 네 가지다.

정렬을 고르는 네 가지 축

축 무엇을 묻는가 없으면 무슨 일이 생기나
시간복잡도 입력이 커질 때 얼마나 느려지나 n이 10만이면 O(n²)는 100억 번을 돈다
안정성(stable) 같은 값끼리의 원래 순서가 지켜지나 2차 정렬이 앞선 정렬을 뭉갠다
적응성(adaptive) 거의 정렬된 입력에서 더 빨라지나 이미 정렬된 데이터를 처음부터 다시 훑는다
제자리(in-place) 추가 메모리를 얼마나 쓰나 데이터만큼의 메모리를 한 번 더 잡는다

안정성이 왜 중요한가

반 아이들을 키순으로 세운다고 해보자. 그런데 키가 똑같은 아이가 둘 있다. 이 둘의 앞뒤 순서를 원래 서 있던 대로 놔두면 안정 정렬이고, 마음대로 뒤바꿔버리면 불안정 정렬이다.

별거 아닌 것 같지만 이게 꽤 중요하다. 성적순으로 한 번 세워둔 줄을 다시 반별로 세운다고 하자. 안정 정렬이면 “반별로 묶이고, 그 안에서는 성적순”이 된다. 불안정 정렬이면 앞에서 해둔 성적순이 통째로 날아간다..

students = [("2반", 90), ("1반", 70), ("2반", 85), ("1반", 95)]

# 1) 성적 높은 순으로 한 번 정렬하고
students.sort(key=lambda s: s[1], reverse=True)
# 2) 반 이름으로 다시 정렬한다
students.sort(key=lambda s: s[0])

print(students)
# [('1반', 95), ('1반', 70), ('2반', 90), ('2반', 85)]
# 반으로 묶였는데 안쪽은 성적순 그대로다 -> 안정 정렬이라 가능한 것

파이썬의 sort()가 안정 정렬이 아니었다면 2번에서 1번 결과가 날아갔을 것이다. 정렬을 두 번 겹쳐 쓸 수 있느냐를 안정성이 결정한다.

시간복잡도는 얼마나 빨리 끝나나 / 안정성은 원래 줄 서 있던 순서를 존중하나 / 적응성은 이미 반쯤 되어 있으면 눈치를 채나

O(n²) 삼형제 — 버블 · 선택 · 삽입

셋 다 최악일 때 O(n²)다. 그런데 성격이 전부 다르다.

버블 정렬 - bubble_sort()

옆에 붙어 있는 두 개를 비교해서 순서가 틀렸으면 자리를 바꾼다. 이걸 끝까지 반복한다. 한 바퀴(패스)를 돌고 나면 가장 큰 값이 맨 뒤에 확정된다. 큰 값이 물 위로 떠오르는 거품 같다고 해서 버블 정렬이다.

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        # 뒤쪽 i칸은 이미 확정됐으니 볼 필요가 없다
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr

arr[j], arr[j+1] = arr[j+1], arr[j] — 파이썬은 자리 바꾸기가 한 줄이다. 오른쪽이 먼저 튜플로 묶인 뒤 왼쪽에 풀리기 때문에 임시 변수가 필요 없다. C++이라면 std::swap을, C#이라면 임시 변수를 하나 둬야 하는 자리다.

[55, 7, 78, 12, 42]를 넣으면 첫 패스 끝에 [7, 55, 12, 42, 78]이 되고, 78이 자기 자리를 찾는다. 그다음 패스는 78을 빼고 앞의 네 칸만 본다.

  • 코딩이 제일 손쉽다. 정렬을 처음 배울 때 여기서 시작하는 이유다
  • 교환이 너무 잦다. 값 하나를 옮기려고 옆 칸과 계속 자리를 바꾼다

선택 정렬 - selection_sort()

남은 값 중에서 가장 작은 걸 골라다가 맨 앞에 갖다 놓는다. 당구공을 정리할 때 번호가 제일 작은 공부터 집어 오는 것과 같다.

def selection_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        min_idx = i

        # i번째 뒤쪽 전체를 훑어 최솟값 위치를 찾는다
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        # 찾은 최솟값을 기준 위치와 한 번만 교환한다
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr

여기가 예전 글에서 틀렸던 곳이다. 안쪽 반복문의 증가식을 j++가 아니라 i++로 써놨었다.. JS로 쓸 땐 반복문 변수를 직접 굴려야 해서 눈에 안 띄었는데, 파이썬의 range(i + 1, n)으로 옮기니 애초에 그런 실수를 할 자리가 없다. 반복 변수를 사람이 굴리지 않는 언어의 이점이 이런 데서 나온다.

  • 교환 횟수가 셋 중 제일 적다. 한 패스에 딱 한 번만 바꾼다
  • 대신 최솟값을 찾으려고 매번 뒤쪽 전체를 다 훑는다. 이미 정렬된 배열을 줘도 똑같이 훑는다 (적응성 X)
  • 멀리 있는 값과 한 번에 자리를 바꾸다 보니 같은 값의 순서가 뒤집힌다 (안정성 X)

삽입 정렬 - insertion_sort()

배열을 정렬된 앞부분과 아직 안 본 뒷부분으로 나눈다. 뒷부분의 맨 앞 값을 하나 꺼내서, 앞부분 안에서 자기가 들어갈 자리를 뒤에서부터 찾아 끼워 넣는다. 손에 든 카드를 정리하는 방식 그대로다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current = arr[i]
        j = i - 1

        # current보다 큰 값들을 한 칸씩 뒤로 민다
        while j >= 0 and arr[j] > current:
            arr[j + 1] = arr[j]
            j -= 1

        # 밀린 자리에 current를 꽂는다
        arr[j + 1] = current

    return arr
[2, 10, 30, 69 16, 8, 31, 22] 상태에서 16을 꺼내면 69 → 30 → 10 순으로 비교하다가 10과 30 사이에 꽂힌다.
  • 이미 정렬된 입력이면 while문이 한 번도 안 돌아 O(n)이다. 적응성이 있는 유일한 O(n²) 정렬이다
  • n이 작을 때는 오히려 퀵 정렬보다 빠르다. 뒤에서 볼 파이썬의 Timsort도 작은 구간은 삽입 정렬로 처리한다

O(n²) 삼형제 중 실전에서 살아남는 건 삽입 정렬 하나다. 나머지 둘은 개념을 이해하기 위한 계단에 가깝다.

카운팅 정렬 — 비교를 아예 하지 않는다

여기부터가 예전 글에 없던 내용이다.

지금까지의 정렬은 전부 두 값을 비교해서 순서를 정했다. 그런데 비교로 정렬하는 방식은 아무리 잘 만들어도 O(n log n) 아래로 못 내려간다는 게 증명돼 있다. 카운팅 정렬은 비교를 아예 포기하고 개수만 센다.

카운팅 정렬 흐름

순서는 이렇다.

  1. 값 하나하나를 리스트의 인덱스로 그대로 쓴다. counts[3]은 “3이 몇 번 나왔나”
  2. counts를 앞에서부터 누적해서 더한다. 그러면 counts[3]은 “3이 들어갈 마지막 자리 번호”가 된다
  3. 원본을 뒤에서부터 훑으면서 그 자리에 값을 놓고, counts를 하나씩 깎는다
def counting_sort(arr, k):
    n = len(arr)
    count_arr = [0] * (k + 1)
    result = [0] * n

    # 1) 값별 등장 횟수를 센다
    for num in arr:
        count_arr[num] += 1

    # 2) 누적합 -> 각 값이 들어갈 마지막 자리
    for i in range(1, k + 1):
        count_arr[i] += count_arr[i - 1]

    # 3) 뒤에서부터 채워야 같은 값의 순서가 지켜진다
    for i in range(n - 1, -1, -1):
        val = arr[i]
        result[count_arr[val] - 1] = val
        count_arr[val] -= 1

    return result


A = [4, 2, 2, 1, 3, 4, 1, 2, 4, 3, 0, 1]
print(counting_sort(A, 4))   # [0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4]

1번은 사실 collections.Counter가 하는 일과 똑같다. 파이썬답게 쓰자면 Counter(arr) 한 줄인데, 여기서는 정렬의 뼈대를 보여주려고 일부러 리스트로 직접 셌다.

3번에서 뒤에서부터 도는 게 핵심이다. range(n - 1, -1, -1)은 “n-1부터 0까지 거꾸로”라는 뜻이다. 앞에서부터 돌면 같은 값끼리 순서가 뒤집혀서 안정성이 깨진다. 처음엔 range(n)으로 써도 결과가 똑같길래 왜 굳이 거꾸로 도나 했는데, 같은 값에 다른 정보가 붙어 있는 경우( 앞의 학생 예시처럼 점수는 같은데 이름이 다른 경우 )를 생각하니 바로 이해가 됐다!

시간복잡도는 O(n + k)다. n은 데이터 개수, k는 값의 최댓값이다.

  • n이 크고 k가 작을 때 압도적으로 빠르다. 시험 점수(0~100), 나이, 등급 같은 데이터
  • 값을 인덱스로 쓰기 때문에 정수(혹은 정수로 바꿀 수 있는 값)만 된다. 실수나 문자열은 못 쓴다
  • k만큼의 리스트를 따로 잡아야 한다. 값이 하나라도 1억이면 1억짜리 리스트가 필요하다.. (제자리 정렬 X)

카운팅 정렬이 빠른 게 아니라, 값의 범위가 좁다는 조건을 미리 알고 있어서 빠른 것이다.

기수 정렬 — 카운팅 정렬을 자릿수마다

카운팅 정렬의 발목을 잡는 건 k다. [170, 45, 802]를 정렬하겠다고 803칸짜리 리스트를 잡을 순 없다.

기수 정렬(Radix Sort)은 값 전체를 보지 않고 자릿수 하나씩 본다. 자릿수는 0~9 열 개뿐이니, 어떤 큰 수가 들어와도 버킷은 항상 열 개다.

기수 정렬 버킷

1의 자리로 나눠 담고 → 순서대로 꺼내고 → 10의 자리로 나눠 담고 → 순서대로 꺼내고, 가장 큰 수의 자릿수만큼 반복하면 정렬이 끝나 있다.

def radix_sort(arr):
    max_value = max(arr)
    current = list(arr)
    k = 1

    # 가장 큰 값에 아직 볼 자릿수가 남아 있는 동안 반복
    while max_value // k > 0:
        digits = [[] for _ in range(10)]

        for num in current:
            digits[(num // k) % 10].append(num)

        # 0번 버킷부터 순서대로 다시 꺼낸다
        current = [num for bucket in digits for num in bucket]
        k *= 10

    return current


print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

버킷을 만들 때 [[] for _ in range(10)]을 쓴 이유가 있다. [[]] * 10으로 쓰면 똑같은 리스트 하나가 10번 참조돼서, 한 버킷에 append하면 열 개가 전부 같이 늘어난다. 파이썬에서 2차원 리스트를 만들 때 제일 자주 밟는 지뢰다.

(num // k) % 10이 자릿수를 뽑는 부분이다. //가 정수 나눗셈이라 170 // 10 = 17이 되고, 여기서 % 10을 하면 7, 즉 170의 10의 자리가 나온다. 이 자리에서 /를 쓰면 실수가 나와 인덱스로 못 쓴다.

그리고 왜 이게 되는지가 한동안 안 잡혔다. 10의 자리로 다시 담을 때 1의 자리 정렬이 망가지지 않는 이유는, 버킷에 앞에서부터 차례로 넣고 앞에서부터 차례로 꺼내기 때문이다. 즉 이 방식 자체가 안정 정렬이고, 안정 정렬을 낮은 자릿수부터 겹쳐 쓰면 결과가 온전히 쌓인다.

기수 정렬은 안정 정렬 위에 서 있다. 안정성이 깨지는 순간 이 알고리즘은 그냥 틀린 답을 낸다.

시간복잡도는 O(d(n + k))다. d는 자릿수, k는 10(버킷 개수). 자릿수가 고만고만하면 사실상 선형이다. 대신 버킷을 따로 잡으니 메모리를 더 쓰고, 음수나 실수는 그대로는 못 넣는다.

기수 정렬은 직접 구현하면서 “언제 멈출 것인가”로 세 번이나 막혔는데, 그 얘기는 C++ - < 1 >에 따로 적었다.

분할 정복 3종 — 병합 · 퀵 · 힙

이 셋은 예전 글에도 있었으니 요점만 다시 짚는다. 셋 다 문제를 반으로 쪼개서 푼다.

병합 정렬 - merge_sort()

배열을 반씩 계속 쪼개서 길이 1이 되면 멈추고, 돌아 나오면서 두 줄을 하나로 합친다. 합칠 때 양쪽 맨 앞을 비교해 작은 쪽을 먼저 가져오면 정렬된 채로 합쳐진다.

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        # 같은 값이면 왼쪽을 먼저 -> 안정성이 여기서 나온다
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    return result + left[i:] + right[j:]


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

<=가 <였다면 같은 값일 때 오른쪽을 먼저 가져와 안정성이 깨진다. 등호 하나가 성질을 바꾸는 자리다.

최악에도 O(n log n)이 보장되고 안정 정렬이다. 대신 합칠 자리를 따로 잡아야 해서 메모리를 n만큼 더 쓴다. 뒤에 나올 파이썬 sorted()의 뿌리가 이 병합 정렬이다.

퀵 정렬 - quick_sort()

기준값(피벗)을 하나 잡고, 그보다 작은 것과 큰 것으로 갈라놓은 뒤 양쪽을 각각 다시 정렬한다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)

리스트 컴프리헨션 덕에 세 줄로 끝난다. 다만 이 방식은 매번 새 리스트를 만들어서 제자리 정렬이 아니다. 원래 퀵 정렬은 배열 안에서 인덱스를 옮겨가며 제자리로 하는 알고리즘인데, 파이썬으로 읽기 좋게 쓰면 이렇게 메모리를 내주게 된다.

평균은 제일 빠르다. 그런데 이미 정렬된 배열에 첫 값을 피벗으로 잡으면 한쪽이 텅 비어서 O(n²)로 떨어진다. 그래서 실전에서는 피벗을 가운데나 무작위로 고른다.

힙 정렬 - heap_sort()

배열을 최대 힙(부모가 자식보다 항상 큰 트리)으로 만들어놓고, 꼭대기(최댓값)를 하나씩 빼서 뒤에 쌓는다.

def heapify(arr, i, size):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2

    if left < size and arr[left] > arr[largest]:
        largest = left
    if right < size and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, largest, size)


def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, i, n)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)

    return arr

최악에도 O(n log n)이면서 추가 메모리를 안 쓴다. 대신 멀리 떨어진 값끼리 교환하다 보니 안정성이 없다.

파이썬에는 heapq 모듈이 이미 들어 있다. heapq.heappush() / heappop()으로 최소 힙을 쓸 수 있고, 우선순위 큐가 필요할 때 직접 짤 일이 거의 없다. ( 다만 heapq는 최소 힙만 지원해서, 최대 힙이 필요하면 값에 마이너스를 붙여 넣는 게 관례다 )

여덟 개를 한 표에

알고리즘 최선 최악 안정성 적응성 제자리 기법 비고
버블 O(n) O(n²) O O O 비교와 교환 코딩이 가장 손쉽다
선택 O(n²) O(n²) X X O 비교와 교환 교환 횟수가 제일 적다
삽입 O(n) O(n²) O O O 비교와 교환 n이 작을 때 효과적
카운팅 O(n+k) O(n+k) O X X 개수 세기 n이 크고 k가 작을 때
기수 O(d(n+k)) O(d(n+k)) O X X 자릿수 분배 정수 전용, 자릿수가 짧을 때
병합 O(n log n) O(n log n) O X X 분할 정복 최악에도 흔들리지 않는다
퀵 O(n log n) O(n²) X X O 분할 정복 평균적으로 가장 빠르다
힙 O(n log n) O(n log n) X X O 선택 + 힙 메모리를 안 쓰는 O(n log n)

이 표를 만들고 나서야 정렬이 왜 이렇게 많은지 납득이 갔다. 한 줄도 다른 줄을 전부 이기지 못한다. 퀵은 최악이 불안하고, 병합은 메모리를 먹고, 힙은 안정성이 없고, 카운팅은 조건이 붙는다. 결국 “제일 좋은 정렬”이 아니라 “지금 내 데이터에 맞는 정렬” 을 고르는 문제였던 것이다!

그런데 실무에서는 sorted() 한 줄이다

여덟 개를 다 짜보고 나서 다시 보니, 파이썬의 sorted()가 왜 저렇게 생겼는지가 보였다.

nums = [170, 45, 75, 90, 802, 24, 2, 66]

sorted(nums)              # 새 리스트를 돌려준다 (원본 그대로)
nums.sort()               # 원본을 제자리에서 바꾼다 (돌려주는 건 None)
sorted(nums, reverse=True)  # 내림차순

sorted()와 list.sort()의 차이가 처음엔 헷갈렸는데, 위의 축으로 보면 명확하다. sort()가 제자리 정렬이고, sorted()는 아니다. 그래서 nums = nums.sort()라고 쓰면 nums에 None이 들어간다. 파이썬 초반에 꼭 한 번은 밟는 함정이다..

key= — 무엇을 기준으로 세울 것인가

앞에서 “키(key)”라는 단어를 정의해뒀는데, 그게 여기 그대로 나온다.

students = [("홍길동", 3, 90), ("김철수", 1, 85), ("이영희", 3, 95)]

# 점수 기준
sorted(students, key=lambda s: s[2])

# 학년 오름차순 + 같은 학년이면 점수 내림차순
sorted(students, key=lambda s: (s[1], -s[2]))

두 번째가 특히 유용하다. key가 튜플을 돌려주면 앞 항목부터 차례로 비교한다. SQL의 ORDER BY 학년 ASC, 점수 DESC와 정확히 같은 일이다. 지난 편에서 Seaborn을 SQL에 대응시켰던 것처럼, 여기서도 익숙한 문법이 그대로 겹친다.

숫자라면 마이너스를 붙여 내림차순을 흉내낼 수 있지만, 문자열에는 못 쓴다. 그럴 땐 안정성을 이용해 두 번 정렬하면 된다. 앞의 학생 예시가 바로 그 방법이었다.

파이썬의 정렬은 Timsort다

sorted()가 안에서 쓰는 알고리즘 이름이 Timsort다. 위에서 만든 표의 여덟 줄 중 병합 정렬과 삽입 정렬을 붙여놓은 구조다.

  • 데이터를 훑으며 이미 정렬돼 있는 구간(run) 을 찾아낸다
  • 구간이 너무 짧으면 삽입 정렬로 늘려 붙인다
  • 그렇게 만든 구간들을 병합 정렬로 합친다
축 Timsort 어디서 왔나
최악 O(n log n) 병합 정렬
안정성 O 병합 정렬
적응성 O run 탐색 + 삽입 정렬
제자리 X 병합 정렬 (메모리를 내준 대가)

표에서 병합 정렬이 갖지 못했던 적응성을 삽입 정렬로 메운 셈이다. 실제 데이터는 완전히 뒤죽박죽인 경우가 드물고 부분적으로 정렬돼 있는 경우가 많은데, Timsort는 그 부분을 찾아내서 건너뛴다. 현실의 데이터가 어떻게 생겼는지를 알고리즘에 박아 넣은 것이라 볼 수 있다.

C++의 std::sort는 정반대 선택을 했다. 퀵 정렬로 가다 깊어지면 힙 정렬로 갈아타는 인트로소트인데, 안정성을 버리고 메모리를 아꼈다. 안정성이 필요하면 std::stable_sort를 따로 쓴다. 자세한 건 C++ - < 1 >에 적어뒀다.

여덟 개를 직접 짤 이유는 실무에서 쓰려고가 아니라, sorted() 안에서 무슨 일이 일어나는지 알기 위해서였다.

다른 언어와 견줘 보면

이번에 정렬을 옮기며 기존 문법과 겹쳐 보였던 지점들을 정리해둔다.

개념 Python 익숙한 다른 문법
자리 바꾸기 a, b = b, a C++ std::swap(a, b), C# (a, b) = (b, a)
반복 변수 자동 관리 for j in range(i+1, n) C++/JS for (j = i+1; j < n; j++)
정수 나눗셈 num // k C++ int / int (타입이 알아서 결정)
표준 정렬 sorted() = Timsort C++ std::sort = 인트로소트
안정 정렬이 필요할 때 그냥 sorted() (기본이 안정) C++ std::stable_sort
정렬 기준 지정 key=lambda s: (s[1], -s[2]) C++ 비교 함수, SQL ORDER BY A, B DESC
힙 / 우선순위 큐 heapq (최소 힙만) C++ std::priority_queue (기본 최대 힙)
2차원 리스트 만들기 [[] for _ in range(10)] C++ vector<vector>(10)

특히 걸렸던 건 마지막 줄이다. C++에서 vector<vector<int>> digits(10)은 독립된 벡터 10개를 만들어주는데, 파이썬에서 [[]] * 10은 같은 리스트를 10번 가리킬 뿐이다. 같은 모양의 코드가 언어마다 다른 뜻이 되는 자리라, 기수 정렬을 두 언어로 옮겨보지 않았으면 그냥 지나쳤을 것 같다.

그리고 sorted()가 안정 정렬이라는 게 파이썬에서는 문서에 보장된 성질이다. C++은 std::sort에 그런 보장이 없다. 이런 건 언어를 옮겨 다닐 때 조용히 사고가 나는 부분이라, 표에 적어두고 기억하려 한다.

한줄 평

  • 1년 반 전에 쓴 글을 다시 읽으니 부끄럽기도 했지만, 그때 남겨둔 덕분에 뭐가 늘었는지 눈에 보여 뿌듯했다!