[자료구조 15] 정렬 알고리즘

정렬(sorting)은 값을 순서대로 늘어놓는 것입니다. 점수를 높은 순으로 세우거나 이름을 가나다순으로 정리하는 일이 모두 정렬입니다. 파이썬에는 이미 훌륭한 정렬 기능이 들어 있지만, 그것을 쓰기 전에 정렬이 안에서 어떻게 이루어지는지 직접 만들어 보는 것이 큰 도움이 됩니다. 이번 글에서는 가장 기본이 되는 세 가지 정렬을 손으로 구현해 보고, 그다음 파이썬 내장 정렬을 제대로 쓰는 법을 익혀 보겠습니다.

15.1 버블 정렬: 이웃끼리 비교하고 교환하기

버블 정렬(bubble sort)은 이웃한 두 값을 비교해 큰 값을 뒤로 보내는 일을 반복합니다. 큰 값이 거품처럼 뒤로 떠오른다고 해서 붙은 이름입니다.

def bubble(a):
a = a[:]
n = len(a)
for i in range(n):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
return a
print(bubble([5, 2, 9, 1, 5, 6]))

[1, 2, 5, 5, 6, 9]

바깥 반복을 한 바퀴 돌 때마다 남은 값 중 가장 큰 것이 맨 뒤로 확정됩니다. 안쪽 반복이 이웃끼리 비교하며 큰 값을 오른쪽으로 밀기 때문입니다. 맨 앞의 a = a[:]는 원본 리스트를 복사해 두어, 정렬이 원본을 건드리지 않게 하는 장치입니다. 반복문이 이중으로 겹쳐 있어 값이 많아지면 느려집니다.

복잡도는 O(n^2)입니다. 값이 10배 많아지면 걸리는 일은 대략 100배로 늘어납니다.

15.2 선택 정렬: 최솟값을 골라 앞으로

선택 정렬(selection sort)은 남은 값 중에서 가장 작은 값을 찾아 앞자리에 놓는 일을 반복합니다. 매번 최소를 골라 채워 나가는 방식입니다.

def selection(a):
a = a[:]
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return a
print(selection([5, 2, 9, 1, 5, 6]))

[1, 2, 5, 5, 6, 9]

안쪽 반복이 남은 구간에서 가장 작은 값의 위치 m을 찾고, 그 값을 현재 앞자리 i와 맞바꿉니다. 첫 바퀴에서 전체 최솟값 1이 맨 앞으로 오고, 다음 바퀴에서 그다음 작은 값 2가 두 번째 자리로 오는 식입니다. 개념은 버블보다 이해하기 쉽지만, 역시 반복이 이중이라 O(n^2)입니다.

15.3 삽입 정렬: 카드를 제자리에 끼우듯

삽입 정렬(insertion sort)은 손에 든 카드를 정렬할 때 하는 방식과 같습니다. 앞부분을 이미 정렬된 상태로 유지하면서, 새 값을 알맞은 자리에 끼워 넣습니다.

def insertion(a):
a = a[:]
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
print(insertion([5, 2, 9, 1, 5, 6]))

[1, 2, 5, 5, 6, 9]

새로 뽑은 값 key보다 큰 값들을 오른쪽으로 한 칸씩 밀어내고, 빈자리에 key를 넣습니다. 앞이 이미 정렬돼 있으니 알맞은 자리를 찾기만 하면 됩니다. 이 정렬은 이미 거의 정렬된 데이터에서는 밀어낼 일이 거의 없어 아주 빠릅니다. 그래서 평균과 최악은 O(n^2)이지만, 최선의 경우는 O(n)입니다.

15.4 파이썬 내장 정렬: sorted와 sort

실무에서는 정렬을 직접 짜지 않습니다. 파이썬에 이미 빠르고 검증된 정렬이 들어 있기 때문입니다. sorted 함수와 리스트의 sort 메서드가 그것입니다.

data = [5, 2, 9, 1, 5, 6]
print(sorted(data)) # 새 리스트 반환
print(sorted(data, reverse=True)) # 내림차순

[1, 2, 5, 5, 6, 9]
[9, 6, 5, 5, 2, 1]

둘의 차이를 아는 것이 중요합니다. sorted()는 정렬된 새 리스트를 돌려주고 원본은 그대로 둡니다. 반면 리스트의 sort() 메서드는 원본 자체를 바꿔 놓습니다. reverse=True를 주면 내림차순이 됩니다. 내부는 팀소트(Timsort)라는 방식이라 O(n log n)으로 동작하며, 앞서 직접 짠 O(n^2) 정렬보다 훨씬 빠릅니다. 값이 많을수록 이 차이는 크게 벌어집니다.

15.5 key로 정렬 기준 정하기

정렬 대상이 단순한 숫자가 아니라 여러 정보를 가진 경우, 무엇을 기준으로 정렬할지 정해야 합니다. 이때 key를 씁니다.

people = [("kim", 30), ("lee", 25), ("park", 28)]
print(sorted(people, key=lambda p: p[1]))

[('lee', 25), ('park', 28), ('kim', 30)]

각 항목은 (이름, 나이) 형태의 튜플입니다. key=lambda p: p[1]은 "각 항목의 두 번째 값, 즉 나이를 기준으로 정렬하라"는 뜻입니다. 그래서 이름 순서가 아니라 나이 오름차순으로 늘어섰습니다. 여기서 lambda는 "받은 값 p에서 p[1]을 꺼내는 짧은 함수"를 그 자리에서 만든 것입니다. 실무 정렬의 대부분이 이 key 형태입니다.

15.6 안정 정렬: 같은 값은 원래 순서를 지킵니다

파이썬 정렬에는 중요한 성질이 하나 더 있습니다. 안정(stable) 정렬이라는 점입니다. 정렬 기준이 같은 값끼리는 원래의 앞뒤 순서가 그대로 유지된다는 뜻입니다.

pairs = [(1, "a"), (2, "b"), (1, "c"), (2, "d")]
print(sorted(pairs, key=lambda p: p[0]))

[(1, 'a'), (1, 'c'), (2, 'b'), (2, 'd')]

첫 번째 값을 기준으로 정렬했습니다. 첫 값이 1인 항목은 (1, 'a')와 (1, 'c') 두 개인데, 정렬 뒤에도 a가 c보다 앞에 있습니다. 원래 순서 그대로입니다. 이 성질은 여러 기준으로 연달아 정렬할 때 요긴합니다. 예를 들어 나이로 정렬한 뒤 다시 지역으로 정렬하면, 같은 지역 안에서는 나이 순서가 보존됩니다.

15.7 정리

버블, 선택, 삽입 정렬은 모두 O(n^2)로, 원리를 이해하는 데 좋은 재료입니다. 이웃끼리 비교하거나(버블), 최소를 골라 오거나(선택), 제자리에 끼우는(삽입) 방식의 차이를 손으로 짜 보면 정렬이 무엇인지 몸에 익습니다. 실전에서는 O(n log n)으로 훨씬 빠르고 안정 정렬인 내장 sorted와 sort를 씁니다. 정렬 기준은 key로 정하면 됩니다. 세 가지 직접 구현과 내장 정렬을 나란히 실행해 결과가 같은지 확인해 보시기 바랍니다.