정렬 기초

🎯 학습 목표

이 강을 마치면 버블·선택·삽입 정렬의 동작을 설명하고 왜 셋 다 O(n²)인지 근거를 댈 수 있습니다. 그리고 정렬의 안정성(stability)이 무엇이며 언제 문제가 되는지, 파이썬 sort()와 sorted()를 key 인자로 자유롭게 쓰는 법을 익히게 됩니다.

실무와 코딩 테스트에서 정렬을 직접 구현할 일은 거의 없습니다. 그래도 배우는 이유는 "O(n²) 알고리즘이 어떻게 생겼는지"를 보는 가장 좋은 교재이기 때문입니다. 그리고 안정성은 실제로 문제 정답을 가릅니다.

💡 O(n²) 정렬 세 가지

세 알고리즘은 접근 방식이 다르지만 모두 n개를 n번 다루므로 O(n²)입니다.

세 가지 정렬의 아이디어

  ① 버블 정렬 — 옆 사람과 비교해서 큰 쪽을 뒤로
     [5, 2, 4, 1]
      ↕            5>2 → 교환   [2, 5, 4, 1]
         ↕         5>4 → 교환   [2, 4, 5, 1]
            ↕      5>1 → 교환   [2, 4, 1, 5]  ← 5가 제자리
     한 바퀴 돌 때마다 가장 큰 값이 뒤로 밀려 간다

  ② 선택 정렬 — 남은 것 중 가장 작은 것을 골라 앞에 놓기
     [5, 2, 4, 1]  최솟값 1 → 맨 앞과 교환   [1, 2, 4, 5]
     [_, 2, 4, 5]  최솟값 2 → 이미 제자리     [1, 2, 4, 5]
     [_, _, 4, 5]  최솟값 4 → 이미 제자리     [1, 2, 4, 5]

  ③ 삽입 정렬 — 카드를 손에 정리하듯 알맞은 자리에 끼우기
     [5 | 2, 4, 1]   2를 5 앞에 끼움   [2, 5 | 4, 1]
     [2, 5 | 4, 1]   4를 5 앞에 끼움   [2, 4, 5 | 1]
     [2, 4, 5 | 1]   1을 맨 앞에 끼움  [1, 2, 4, 5]

  ▲ 왜 전부 O(n²)인가
    "n개 각각에 대해, 나머지 n개를 훑는다"
    → n × n

  ▲ 그래도 차이는 있다
    · 삽입 정렬은 이미 정렬된 입력에서 O(n) — 거의 안 움직인다
    · 선택 정렬은 어떤 입력이든 항상 O(n²) — 교환 횟수는 가장 적다
    · 버블 정렬은 교환이 가장 많다 — 실무에서 거의 안 쓴다

정렬	최선	평균·최악	안정성	추가 메모리
버블	O(n)	O(n²)	안정	O(1)
선택	O(n²)	O(n²)	불안정	O(1)
삽입	O(n)	O(n²)	안정	O(1)

삽입 정렬의 최선 O(n)이 의외로 중요합니다. 거의 정렬된 데이터에서는 매우 빠르기 때문에, 실제 정렬 라이브러리들이 작은 구간을 처리할 때 삽입 정렬을 섞어 씁니다. 9강에서 다시 나옵니다.

📖 안정 정렬이 왜 중요한가

안정 정렬(stable sort)은 값이 같은 원소들의 원래 순서를 그대로 유지하는 정렬입니다. 말로는 사소해 보이지만, 두 가지 기준으로 정렬할 때 결정적입니다.

안정성이 결과를 바꾸는 예

  학생 데이터 (입력 순서대로)
   ("김", 90), ("이", 85), ("박", 90), ("최", 85)

  점수 내림차순으로 정렬하면?

  [안정 정렬]  같은 점수는 원래 순서 유지
   ("김", 90), ("박", 90), ("이", 85), ("최", 85)
       ↑ 김이 박보다 먼저 (입력 순서 그대로)

  [불안정 정렬]  같은 점수의 순서는 보장 안 됨
   ("박", 90), ("김", 90), ("최", 85), ("이", 85)
       ↑ 순서가 뒤집힐 수 있다

  ▲ 이것이 왜 유용한가 — 다중 기준 정렬

   "점수 내림차순, 점수가 같으면 이름 오름차순"

   안정 정렬이면 두 번 정렬하면 된다
    1) 이름 오름차순으로 정렬
    2) 점수 내림차순으로 정렬
       → 점수가 같은 것들은 1번의 이름 순서가 그대로 남는다

   ※ 순서가 중요하다. '덜 중요한 기준'부터 정렬한다.

  ▲ 파이썬의 sort()·sorted() 는 안정 정렬이다.
    공식 문서에 명시돼 있으므로 믿고 활용할 수 있다.

물론 파이썬에서는 key 하나로 다중 기준을 한 번에 지정하는 방법도 있습니다. 다음 예제에서 두 방식을 모두 보겠습니다.

💻 실전 예제 — 직접 구현과 파이썬 정렬

def insertion_sort(arr):
    """삽입 정렬 — 원본을 직접 정렬한다"""
    for i in range(1, len(arr)):
        key = arr[i]                    # 끼워 넣을 값
        j = i - 1
        while j >= 0 and arr[j] > key:  # 나보다 큰 값들을
            arr[j + 1] = arr[j]         # 한 칸씩 뒤로 민다
            j -= 1
        arr[j + 1] = key                # 빈 자리에 넣는다
    return arr


def selection_sort(arr):
    """선택 정렬 — 남은 구간의 최솟값을 앞으로"""
    n = len(arr)
    for i in range(n):
        min_idx = 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


students = [("김", 90), ("이", 85), ("박", 90), ("최", 85)]

# 방법 1 : key 하나로 다중 기준 (점수 내림차순, 이름 오름차순)
by_key = sorted(students, key=lambda s: (-s[1], s[0]))

# 방법 2 : 안정 정렬을 이용해 두 번 나눠서
tmp = sorted(students, key=lambda s: s[0])          # 덜 중요한 기준 먼저
by_two_pass = sorted(tmp, key=lambda s: s[1], reverse=True)

print(insertion_sort([5, 2, 4, 1]))   # [1, 2, 4, 5]
print(selection_sort([5, 2, 4, 1]))   # [1, 2, 4, 5]
print(by_key)                          # 두 결과가 같다
print(by_key == by_two_pass)           # True

코드를 줄 단위로 보겠습니다.

• for i in range(1, len(arr)) — 삽입 정렬은 0번은 이미 정렬된 것으로 보고 1번부터 시작합니다.
• while j >= 0 and arr[j] > key — 왼쪽으로 가면서 key보다 큰 값을 계속 뒤로 밉니다. j >= 0을 먼저 확인해야 인덱스 오류가 안 납니다.
• arr[j] > key에서 등호를 넣지 않는 것이 안정성의 비결입니다. 같은 값을 만나면 멈추므로 원래 순서가 보존됩니다. >=로 바꾸면 불안정해집니다.
• arr[i], arr[min_idx] = arr[min_idx], arr[i] — 파이썬의 동시 할당으로 임시 변수 없이 교환합니다.
• 선택 정렬의 이 교환이 멀리 떨어진 원소를 건너뛰며 옮기기 때문에 같은 값의 순서가 뒤바뀔 수 있습니다. 그래서 불안정합니다.
• key=lambda s: (-s[1], s[0]) — 튜플을 반환하면 앞 요소부터 차례로 비교합니다. 점수에 음수를 붙여 내림차순을 만들고, 같으면 이름 오름차순으로 갑니다. 숫자에만 쓸 수 있는 기법입니다.
• sorted(tmp, key=..., reverse=True) — 두 번 정렬하는 방식입니다. 안정 정렬이기 때문에 첫 정렬 결과가 유지됩니다. 문자열을 내림차순으로 해야 할 때처럼 음수를 쓸 수 없는 경우에 유용합니다.

sort()와 sorted()의 차이도 정리해 두겠습니다. lst.sort()는 원본을 바꾸고 None을 반환합니다. sorted(lst)는 새 리스트를 만들어 반환하고 원본은 그대로입니다. a = lst.sort()라고 쓰면 a가 None이 되는 실수가 매우 흔합니다.

⚠️ 자주 하는 실수

첫째, sort()의 반환값을 씁니다. sorted_list = my_list.sort()는 None을 담습니다. 원본을 바꾸려면 lst.sort(), 새 리스트가 필요하면 sorted(lst)입니다.

둘째, key와 cmp를 헷갈립니다. 파이썬 3에는 두 값을 비교하는 cmp 인자가 없습니다. key는 "각 원소를 무엇으로 볼 것인가"를 지정하는 함수입니다. 꼭 비교 함수가 필요하면 functools.cmp_to_key로 감싸야 합니다.

셋째, 정렬을 반복문 안에서 합니다. sorted()는 O(n log n)입니다. 반복문 안에 넣으면 전체가 O(n² log n)이 됩니다. 한 번만 정렬해 두고 재사용하는 구조로 바꾸세요.

넷째, 안정성을 확인하지 않고 두 번 정렬합니다. 다중 기준을 두 번의 정렬로 처리하려면 덜 중요한 기준을 먼저 정렬해야 합니다. 순서를 반대로 하면 결과가 완전히 달라집니다.

다섯째, 자료형이 섞인 리스트를 정렬합니다. [1, "a"]처럼 비교할 수 없는 자료형이 섞이면 오류가 납니다. 입력을 받을 때 정수로 변환했는지 확인하세요. 문자열 "10"과 "9"를 정렬하면 "10"이 앞에 옵니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	버블·선택·삽입은 전부 O(n²)
2	삽입 정렬은 거의 정렬된 입력에서 O(n)
3	안정 정렬은 같은 값의 원래 순서를 지킨다
4	파이썬 정렬은 안정하다
5	다중 기준은 key에 튜플을 돌려주면 된다
6	두 번 정렬할 땐 덜 중요한 기준부터
7	sort()는 원본 변경, sorted()는 새 리스트

지금 해 볼 것은 students를 이름 오름차순으로 먼저 정렬하지 않고 점수만 정렬해 보는 것입니다. 안정 정렬 덕분에 입력 순서가 그대로 남는 것을 직접 확인할 수 있습니다.

다음 9강 「효율적 정렬」에서는 O(n log n) 정렬로 넘어갑니다. 병합 정렬과 퀵 정렬이 어떻게 log n을 만들어 내는지, 그리고 파이썬 sort()의 내부 알고리즘이 무엇인지 다루겠습니다.

📚 참고 자료

• Sorting Techniques — Python 공식 문서
• sorted() — Python 공식 문서
• functools.cmp_to_key — Python 공식 문서