기초 정렬: 버블, 선택, 삽입
sorted() 한 줄로 끝나는 정렬도 안에서는 두 값을 비교하고 자리를 교환하는 일을 되풀이합니다. 가장 쉬운 세 방법을 막대 8개로 한 걸음씩 따라가며, 몇 번 비교하고 몇 번 교환하는지 세어 보세요.
한 줄 답. 세 방법 모두 두 값을 비교하고, 순서가 틀렸으면 교환을 되풀이합니다. 버블은 이웃끼리 비교해 큰 값을 오른쪽 끝으로 밀어내고, 선택은 남은 것에서 가장 작은 값을 골라 앞에 놓고, 삽입은 하나씩 꺼내 앞쪽의 정렬된 줄에 끼워 넣습니다. 셋 다 n 이 두 배면 일이 네 배쯤 늘어(O(n²)) 큰 입력에는 맞지 않지만, 작은 입력이나 거의 정렬된 입력에서는 삽입 정렬이 빠릅니다.
방법을 고르고 「다음」을 누르면 한 걸음씩 나아갑니다. 비교하는 걸음과 교환하는 걸음은 따로입니다. 파랑 막대와 양쪽 화살표는 지금 비교하는 둘이고, 화살표 위에 7 < 8 처럼 비교한 결과를 적습니다. 주황 막대와 서로 건너가는 굽은 화살표 둘은 방금 교환한 둘입니다. 보라 이름표는 선택 정렬의 「가장 작음」(지금까지 가장 작은 것)과 삽입 정렬의 「끼우는 값」입니다. 초록 막대와 아래 괄호는 자리를 잡은 구간입니다. 삽입 정렬의 괄호는 「앞부분끼리 정렬됨」이라, 끝나기 전에 다시 자리가 밀릴 수 있습니다. 처음 막대는 5, 2, 7, 1, 8, 3, 6, 4 입니다.
해 볼 것. ① 버블 정렬로 끝까지 넘기면 25 번 비교하고 13 번 교환합니다(40 걸음). 넷째 패스(pass, 한 바퀴)에서 이미 다 정렬되지만, 다섯째 패스를 돌며 한 번도 교환하지 않은 것을 보고서야 멈춥니다. ② 선택 정렬은 28 번 비교하고 5 번만 교환합니다. 「교환」은 한 패스에 많아야 한 번 나옵니다. ③ 삽입 정렬은 18 번 비교하고 13 번 교환합니다. 교환 횟수가 버블과 같은 13 입니다(4절에서 까닭을 봅니다).
1. 세 방법의 생각
정렬은 값들을 작은 것부터 늘어놓는 일입니다. 이 쪽의 세 방법은 모두 두 가지 일만 합니다. 비교(compare, 두 값 가운데 어느 것이 큰가)와 교환(swap, 두 자리의 값을 맞바꾸기)입니다. 일의 양은 이 두 횟수로 셉니다.
| 방법 | 생각 한 줄 | 한 패스에 하는 일 |
|---|---|---|
| 버블 정렬 | 이웃한 둘을 비교해 큰 값을 오른쪽으로 밀어낸다. 한 패스 돌면 가장 큰 값이 거품처럼 오른쪽 끝에 떠오른다 | a[j] > a[j+1] 이면 교환을 왼쪽부터 끝까지. 한 패스 동안 한 번도 교환하지 않으면 멈춘다 |
| 선택 정렬 | 남은 것을 다 훑어 가장 작은 값을 고르고(선택) 남은 것의 맨 앞에 놓는다 | 남은 것에서 최솟값 찾기, 그다음 맨 앞과 교환 한 번 |
| 삽입 정렬 | 카드를 손에 쥐듯, 왼쪽은 정렬된 줄로 두고 다음 값을 꺼내 알맞은 자리에 끼운다 | 꺼낸 값의 왼쪽 이웃이 더 크면 교환을, 더 크지 않을 때까지 되풀이 |
2. 손으로 따라가기
실험의 처음 막대 5, 2, 7, 1, 8, 3, 6, 4 를 삽입 정렬로 끝까지 따라갑니다. 세로줄 | 왼쪽이 정렬된 앞부분입니다.
| 패스 | 꺼낸 값 | 비교한 왼쪽 이웃 | 패스가 끝난 뒤 | 비교 | 교환 | 멈춘 까닭 |
|---|---|---|---|---|---|---|
| 1 | 2 | 5 | 2 5 | 7 1 8 3 6 4 | 1 | 1 | 맨 앞에 닿음 |
| 2 | 7 | 5 | 2 5 7 | 1 8 3 6 4 | 1 | 0 | 5 < 7 |
| 3 | 1 | 7, 5, 2 | 1 2 5 7 | 8 3 6 4 | 3 | 3 | 맨 앞에 닿음 |
| 4 | 8 | 7 | 1 2 5 7 8 | 3 6 4 | 1 | 0 | 7 < 8 |
| 5 | 3 | 8, 7, 5, 2 | 1 2 3 5 7 8 | 6 4 | 4 | 3 | 2 < 3 |
| 6 | 6 | 8, 7, 5 | 1 2 3 5 6 7 8 | 4 | 3 | 2 | 5 < 6 |
| 7 | 4 | 8, 7, 6, 5, 3 | 1 2 3 4 5 6 7 8 | 5 | 4 | 3 < 4 |
| 합 | 18 | 13 |
「멈춘 까닭」의 5 < 7 은 왼쪽 이웃 5 가 꺼낸 값 7 보다 크지 않다는 뜻입니다. 그러면 교환하지 않고 멈춥니다.
왼쪽 이웃이 더 크지 않으면(패스 2, 4 의 7, 패스 5 의 2) 거기서 멈춥니다. 앞부분은 이미 정렬돼 있어서 더 왼쪽은 볼 필요가 없습니다. 맨 앞에 닿아도 멈춥니다(패스 1, 3).
같은 입력을 버블 정렬은 패스마다 이렇게 교환합니다: 2 5 1 7 3 6 4 8 → 2 1 5 3 6 4 7 8 → 1 2 3 5 4 6 7 8 → 1 2 3 4 5 6 7 8 → 다섯째 패스는 교환 없음, 멈춤. 모두 25 번 비교하고 13 번 교환합니다. 선택 정렬은 28 번 비교하고 5 번 교환합니다.
3. 입력 모양에 따라 달라진다
| 방법 | 비교 횟수 | 교환 횟수 |
|---|
입력은 1 ~ n 의 수입니다. 「뒤섞임」은 고정 씨앗으로 섞어 열 때마다 같습니다. 「거의 정렬됨」은 정렬된 줄에서 두 값의 자리를 n ÷ 16 번(적어도 한 번) 교환한 것입니다. 막대의 길이는 최악의 경우의 비교 횟수 n(n − 1) ÷ 2 와 비교한 비율입니다.
해 볼 것. ① 처음(뒤섞임, n = 32)에는 버블 468 번 비교하고 263 번 교환, 선택 496 번과 31 번, 삽입 290 번과 263 번입니다. ② 「거의 정렬됨」으로 바꾸면 삽입은 51 번 비교하고 20 번 교환합니다. 버블은 196 번 비교하고, 선택은 그대로 496 번 비교합니다. ③ 「이미 정렬됨」에서는 버블과 삽입이 31 번(n − 1) 비교하고 하나도 교환하지 않습니다. 선택은 여전히 496 번 비교합니다. ④ 「거꾸로」에서는 버블과 삽입 모두 496 번 비교하고 496 번 교환합니다. 선택은 496 번 비교하고 16 번만 교환합니다. ⑤ 뒤섞임에서 n 을 64 로 올리면 삽입이 1015 번 비교합니다. n 이 두 배가 되자 290 에서 1015 로 3.5 배쯤 늘었습니다. 선택은 496 에서 2016 으로, 정확히 n(n − 1) ÷ 2 입니다.
걸리는 시간이 n 에 따라 어떻게 늘어나는지 읽는 법은 시간 복잡도 쪽에 있습니다. n(n − 1) ÷ 2 는 n 이 두 배면 네 배쯤 되므로 O(n²) 이라고 적습니다.
4. 꼭 알아야 할 성질
| 성질 | 버블 | 선택 | 삽입 |
|---|---|---|---|
| 비교 횟수 | n − 1 ~ n(n − 1) ÷ 2 | 늘 n(n − 1) ÷ 2 | n − 1 ~ n(n − 1) ÷ 2 |
| 교환 횟수 | 역순 쌍의 수 | 많아야 n − 1 | 역순 쌍의 수 |
| 거의 정렬된 입력에서 | 조금 빨라진다. 작은 값이 뒤에 있으면 한 패스에 한 칸씩만 앞으로 와서 느리다 | 그대로 | 빠르다 |
| 안정 정렬(5절) | 예 | 아니요 | 예 |
| 제자리 정렬(6절) | 예 | 예 | 예 |
역순 쌍(inversion)은 앞에 있는 값이 뒤에 있는 값보다 큰 쌍입니다. 5, 2, 7, 1, 8, 3, 6, 4 에는 13 쌍이 있습니다(5 와 2, 5 와 1, …). 이웃한 둘을 교환하면 그 두 값의 순서만 바뀌므로 역순 쌍이 꼭 하나 줄어듭니다. 그래서 이웃끼리만 교환하는 버블과 삽입은 교환 횟수가 역순 쌍의 수와 같습니다. 삽입 정렬은 패스마다 「교환 횟수 + 멈출 때 한 번」만 비교하므로, 비교 횟수가 역순 쌍의 수 이상, 역순 쌍의 수 + n − 1 이하입니다. 거의 정렬된 입력은 역순 쌍이 적어서 삽입 정렬이 n 에 가까운 횟수로 끝납니다.
선택 정렬은 입력이 어떻든 남은 것을 끝까지 훑어야 최솟값을 알 수 있어 비교 횟수가 늘 같습니다. 대신 패스마다 많아야 한 번 교환합니다. 이 쪽은 최솟값이 이미 제자리면 교환하지 않고 세지도 않습니다(algs4 책은 늘 교환하는 것으로 세어 n 번이라고 적습니다).
5. 안정 정렬: 같은 값의 순서가 지켜지는가
값이 같은 것들이 정렬한 뒤에도 정렬 전의 순서를 그대로 지키면 안정 정렬입니다. 숫자만 정렬할 때는 차이가 보이지 않지만, 주문을 고객 이름으로 정렬하는 것처럼 「값」이 자료의 한 칸일 때 중요합니다. 날짜순으로 놓인 주문을 고객 이름으로 다시 정렬하면, 안정 정렬에서는 같은 고객의 주문이 날짜순으로 남습니다. Python 의 sorted 와 list.sort 는 안정 정렬임을 보장해서, 여러 기준 정렬을 정렬 여러 번으로 만들 수 있습니다(출처의 Python 문서).
- 버블: 안정. 왼쪽이 더 클 때만 교환합니다. 같은 값끼리는 교환하지 않으니 서로를 넘어가지 않습니다.
- 삽입: 안정. 꺼낸 값은 왼쪽 이웃이 더 클 때만 왼쪽으로 갑니다. 같은 값을 만나면 그 뒤에서 멈춥니다.
- 선택: 안정이 아니다. 멀리 떨어진 둘을 교환하다가 같은 값을 건너뜁니다. 예:
[2ᵃ, 2ᵇ, 1]에서 가장 작은 1 을 맨 앞의 2ᵃ 와 교환하면[1, 2ᵇ, 2ᵃ]가 되어 두 2 의 순서가 뒤집힙니다.
버블과 삽입도 「더 크면 교환한다」를 「크거나 같으면 교환한다」로 쓰면 같은 값끼리 교환하게 되어 안정이 깨집니다. 부등호 하나가 성질을 정합니다.
6. 제자리 정렬
받은 배열 안에서 자리만 교환하고, 따로 드는 메모리가 값 몇 개(지금 위치, 최솟값의 자리)뿐이면 제자리 정렬입니다. 세 방법 모두 그렇습니다. 배열 하나만큼 메모리가 더 드는 방법도 있습니다(병합 정렬). Python 에서는 list.sort() 가 리스트를 그 자리에서 바꾸고, sorted() 는 정렬한 새 리스트를 만들어 돌려줍니다.
7. 언제 무엇을 쓰나
| 방법 | 최선의 경우 | 평균의 경우 | 최악의 경우 | 더 드는 메모리 | 쓰는 경우 |
|---|---|---|---|---|---|
| 버블 정렬 | 이미 정렬됨: n − 1 번 비교. n 이 두 배면 두 배(O(n)) | n 이 두 배면 네 배(O(n²)) | 거꾸로: n(n − 1) ÷ 2 번 비교하고 그만큼 교환. O(n²) | 값 몇 개(O(1)) | 배울 때. 같은 자리에서는 삽입 정렬이 낫다 |
| 선택 정렬 | 입력과 상관없이 n(n − 1) ÷ 2 번 비교. O(n²). 교환은 많아야 n − 1 번 | 값 몇 개(O(1)) | 교환(쓰기)이 비교보다 훨씬 비쌀 때 | ||
| 삽입 정렬 | 이미 정렬됨: n − 1 번 비교. O(n) | 뒤섞임: 비교와 교환이 n²/4 쯤. O(n²) | 거꾸로: n(n − 1) ÷ 2 번 비교하고 그만큼 교환. O(n²) | 값 몇 개(O(1)) | 작은 입력, 거의 정렬된 입력, 정렬된 줄에 값을 하나씩 더할 때 |
표준 라이브러리sorted, list.sort | 큰 입력에서도 n log n 쯤. 자세히는 병합·퀵 정렬 쪽 | 방법에 따라 다름 | 실무의 거의 모든 경우. 안정 정렬 | ||
8. 코드
def bubble_sort(a):
for end in range(len(a) - 1, 0, -1):
swapped = False
for j in range(end):
if a[j] > a[j + 1]: # 이웃끼리 비교해 큰 값을 뒤로
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 한 번도 교환하지 않았으면 이미 정렬됨
break
return a
def selection_sort(a):
for i in range(len(a) - 1):
low = i
for j in range(i + 1, len(a)): # 남은 것 가운데 가장 작은 값을 찾는다
if a[j] < a[low]:
low = j
a[i], a[low] = a[low], a[i] # 멀리 건너뛰어 교환한다(안정하지 않다)
return a
def insertion_sort(a):
for i in range(1, len(a)):
j = i
while j > 0 and a[j - 1] > a[j]: # 왼쪽 이웃이 더 클 때만 교환한다(안정)
a[j - 1], a[j] = a[j], a[j - 1]
j -= 1
return a
print(bubble_sort([5, 2, 7, 1, 8, 3, 6, 4])) # [1, 2, 3, 4, 5, 6, 7, 8]
print(selection_sort([5, 2, 7, 1, 8, 3, 6, 4])) # [1, 2, 3, 4, 5, 6, 7, 8]
print(insertion_sort([5, 2, 7, 1, 8, 3, 6, 4])) # [1, 2, 3, 4, 5, 6, 7, 8]
print(sorted([5, 2, 7, 1, 8, 3, 6, 4])) # 실무에서는 이 한 줄
어디에 쓰나
- 작은 입력. 값이 적으면 O(n²) 도 금방 끝나고, 코드가 짧아 틀리기 어렵습니다.
- 거의 정렬된 자료. 이미 정렬된 목록에 값 몇 개가 끼어든 경우 삽입 정렬은 n 에 가까운 횟수로 끝납니다.
- 쓰기가 비싼 곳. 자리를 옮기는 일이 비교보다 훨씬 비싸면 교환이 가장 적은 선택 정렬을 고릅니다.
- 정렬을 배우는 출발점. 비교 횟수와 교환 횟수 세기, 안정 정렬, 제자리 정렬은 병합·퀵 정렬과 힙에서 그대로 다시 나옵니다.
자주 묻는 것
이 세 정렬을 실무에서 직접 짜서 쓰나요?
거의 없습니다. 보통은 언어의 표준 정렬(Python 의 sorted 와 list.sort)을 씁니다. 이 셋을 배우는 까닭은 비교 횟수와 교환 횟수를 세는 법, 안정 정렬과 제자리 정렬 같은 말을 가장 작은 예로 익히기 위해서입니다. 큰 입력을 빨리 정렬하는 방법은 병합 정렬과 퀵 정렬 쪽에서 봅니다.
버블 정렬과 삽입 정렬은 무엇이 다른가요?
둘 다 이웃끼리만 교환해서 교환 횟수는 역순 쌍의 수로 같습니다. 다른 것은 비교 횟수입니다. 이 쪽의 실험(n 8 ~ 64, 네 가지 모양)에서는 버블이 삽입보다 적게 비교한 경우가 없었고, 거의 정렬된 입력에서는 차이가 컸습니다(n = 32 에서 196 번과 51 번).
안정 정렬은 언제 중요한가요?
여러 기준으로 정렬할 때입니다. 둘째 기준으로 먼저 정렬하고 첫째 기준으로 다시 정렬하면, 안정 정렬에서는 첫째 기준이 같은 것끼리 둘째 기준의 순서가 남습니다. Python 의 sorted 와 list.sort 는 안정 정렬임을 보장하므로 이 방법을 쓸 수 있습니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 두 값 가운데 어느 것이 큰가 보기 | 비교(compare) |
| 두 자리의 값을 맞바꾸기 | 교환(exchange, swap) |
| 한 바퀴 | 패스(pass) |
| 이웃끼리 비교해 큰 값을 밀어내기 | 버블 정렬(bubble sort) |
| 가장 작은 것을 골라 앞에 놓기 | 선택 정렬(selection sort) |
| 정렬된 줄에 끼워 넣기 | 삽입 정렬(insertion sort) |
| 앞이 뒤보다 큰 쌍 | 역순 쌍, 반전(inversion) |
| 거의 정렬된 입력 | 부분적으로 정렬된 배열(partially sorted array) |
| 같은 값의 순서가 지켜짐 | 안정 정렬(stable sort) |
| 받은 배열 안에서만 정렬 | 제자리 정렬(in-place sort) |
| n 이 두 배면 네 배 | O(n²), 이차 시간(quadratic time) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms, 4th ed., 2.1 Elementary Sorts. 견주기와 바꾸기로 일을 세는 법, 제자리 정렬, 선택 정렬과 삽입 정렬의 견준 횟수·바꾼 횟수, 뒤바뀐 쌍과 부분적으로 정렬된 배열.
- Python 문서, Sorting Techniques.
sorted와list.sort, 정렬이 안정임을 보장한다는 것, 여러 기준 정렬을 정렬 여러 번으로 만드는 법.