C로 보는 버블 정렬: 한 줄씩 따라가는 동작 원리
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
swapped = 1;
}
}
if (!swapped) break; // 교환이 없으면 이미 정렬됨
}
}- n
- 7
- i
- 0
- j
- -
- swapped
- 0
- 비교 중
- 방금 교환
- 자리 확정
모든 단계 보기
- L21번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
- L5a[0] = 5 와 a[1] = 1 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L5a[1] = 5 와 a[2] = 4 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L5a[2] = 5 와 a[3] = 2 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L5a[3] = 5 와 a[4] = 8 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L5a[4] = 8 와 a[5] = 3 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L5a[5] = 8 와 a[6] = 6 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L12바퀴가 끝났습니다. a[6] = 8 은 자리가 확정됐습니다.
- L22번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
- L5a[0] = 1 와 a[1] = 4 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L5a[1] = 4 와 a[2] = 2 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L5a[2] = 4 와 a[3] = 5 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L5a[3] = 5 와 a[4] = 3 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L5a[4] = 5 와 a[5] = 6 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L12바퀴가 끝났습니다. a[5] = 6 은 자리가 확정됐습니다.
- L23번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
- L5a[0] = 1 와 a[1] = 2 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L5a[1] = 2 와 a[2] = 4 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L5a[2] = 4 와 a[3] = 3 를 비교합니다. 앞이 더 크니 바꿉니다.
- L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
- L5a[3] = 4 와 a[4] = 5 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L12바퀴가 끝났습니다. a[4] = 5 은 자리가 확정됐습니다.
- L24번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
- L5a[0] = 1 와 a[1] = 2 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L5a[1] = 2 와 a[2] = 3 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L5a[2] = 3 와 a[3] = 4 를 비교합니다. 순서가 맞으니 그대로 둡니다.
- L12이번 바퀴에서 한 번도 바꾸지 않았습니다. 이미 정렬되었으니 멈춥니다.
목차
버블 정렬은 이웃한 두 칸을 비교해서 순서가 틀리면 바꾸고, 이 일을 배열이 정렬될 때까지 되풀이합니다. 위 그림은 [5, 1, 4, 2, 8, 3, 6] 을 이 코드로 정렬하는 과정입니다. 다음 버튼을 누를 때마다 실행 중인 줄, 변수 i · j · swapped, 배열이 함께 바뀝니다. 이 입력은 4바퀴째에 멈춥니다.
한 바퀴가 하는 일
바깥 for 문이 한 번 도는 것을 한 바퀴라고 부르겠습니다. 한 바퀴 동안 안쪽 for 문이 j 를 0부터 하나씩 늘리며 a[j] 와 a[j + 1] 을 비교합니다. 앞의 값이 더 크면 임시 변수 t 에 잠깐 옮겨 두고 두 값을 맞바꾼 뒤 swapped 를 1로 바꿉니다.
1바퀴를 시작합니다. j = 0부터 이웃한 두 칸을 차례로 비교합니다.
모든 단계 보기
- 1바퀴를 시작합니다. j = 0부터 이웃한 두 칸을 차례로 비교합니다.
- j = 0: 5가 1보다 커서 두 값을 바꿉니다.
- j = 1: 5가 4보다 커서 두 값을 바꿉니다.
- j = 2: 5가 2보다 커서 두 값을 바꿉니다.
- j = 3: 5는 8보다 작아서 그대로 둡니다.
- j = 4: 8이 3보다 커서 두 값을 바꿉니다.
- j = 5: 8이 6보다 커서 두 값을 바꿉니다. 8이 a[6]에 자리를 잡고 1바퀴가 끝납니다.
1바퀴에서 5는 1, 4, 2를 차례로 지나 a[3] 까지 갑니다. 거기서 더 큰 8을 만나 멈추고, 그 뒤로는 8이 3과 6을 넘어 맨 끝에 닿습니다. 비교 6번 중 교환이 5번입니다.
가장 큰 값이 끝에 모이는 이유
한 바퀴 동안 가장 큰 값을 만나면, 그 값은 오른쪽 이웃보다 작을 수 없습니다. 이웃보다 크면 바꾸어 한 칸 오른쪽으로 갑니다. 이웃이 같은 값이면 그대로 두지만, 비교는 그 같은 값으로 이어지므로 결과는 같습니다. 어느 쪽이든 가장 큰 값은 비교가 진행되는 방향을 따라 오른쪽으로 계속 밀려갑니다.
그래서 바퀴가 끝나면 정렬되지 않은 구간의 가장 큰 값이 그 구간의 맨 끝에 놓입니다. 끝에 놓인 값은 이후 바퀴에서 다시 움직이지 않습니다. 안쪽 for 문의 조건이 j < n - 1 - i 인 것도 이 때문입니다. 바퀴마다 확정된 칸을 하나씩 빼고 비교하니 비교 횟수가 하나씩 줄어듭니다.
바퀴는 많아야 n − 1번
한 바퀴가 끝날 때마다 값 하나가 제자리를 찾습니다. 값 n개 중 n − 1개가 자리를 잡으면 남은 하나는 저절로 맨 앞에 있습니다. 그래서 바깥 for 문은 i < n - 1 까지만 돕니다. 값이 7개면 많아야 6바퀴입니다.
기본 입력에서 비교 횟수는 6, 5, 4, 3으로 바퀴마다 하나씩 줄고, 교환은 5, 2, 1, 0번입니다. 모두 합하면 비교 18번, 교환 8번입니다.
swapped로 일찍 멈추기
어떤 바퀴에서 한 번도 바꾸지 않았다면, 이웃한 값이 모두 순서대로 놓여 있다는 뜻입니다. 배열이 이미 정렬된 것입니다. 12번 줄의 if (!swapped) break; 가 이때 바깥 반복을 끝냅니다.
위 그림을 다시 보면 기본 입력은 3바퀴가 끝났을 때 이미 정렬되어 있습니다. 그래도 코드는 그 사실을 바로 알지 못합니다. 4바퀴에서 3번 비교해 보고 교환이 없다는 것을 확인한 뒤에야 멈춥니다.
이미 정렬된 입력이 가장 좋은 경우입니다. 첫 바퀴에서 n − 1번 비교하고 끝납니다.
비교 횟수와 시간 복잡도
가장 나쁜 경우는 거꾸로 정렬된 입력입니다. 비교할 때마다 바꾸게 되니 swapped 가 0이 되는 바퀴가 없고, n − 1바퀴를 모두 돕니다. 비교 횟수는 (n − 1) + (n − 2) + … + 1 = n(n − 1) / 2 입니다.
| 입력 | 바퀴 | 비교 | 교환 |
|---|---|---|---|
| 1, 2, 3, 4, 5, 6, 7 (정렬됨) | 1 | 6 | 0 |
| 5, 1, 4, 2, 8, 3, 6 (기본 입력) | 4 | 18 | 8 |
| 7, 6, 5, 4, 3, 2, 1 (거꾸로) | 6 | 21 | 21 |
비교 횟수 n(n − 1) / 2 는 n² 에 비례해 늘어납니다. 그래서 가장 나쁜 경우와 평균적인 경우의 시간 복잡도는 O(n²) 입니다. 가장 좋은 경우는 비교 n − 1번이면 끝나므로 O(n) 입니다.
안정 정렬이고 제자리 정렬이다
5번 줄은 앞의 값이 뒤의 값보다 클 때만 바꿉니다. 같은 값끼리는 바꾸지 않으므로, 같은 값이 처음에 놓여 있던 순서가 정렬 뒤에도 그대로 남습니다. 이런 정렬을 안정 정렬이라고 합니다.
값을 배열 안에서 맞바꾸기만 하므로 추가로 쓰는 메모리는 변수 t, i, j, swapped 뿐입니다. 입력이 커져도 추가 메모리는 늘지 않으니 제자리 정렬이기도 합니다.
다시 정리하면
버블 정렬은 이웃한 두 칸만 보고 바꾸는 단순한 규칙으로, 바퀴마다 남은 값 중 가장 큰 값을 끝으로 보냅니다. 바퀴는 많아야 n − 1번이고, 교환이 없는 바퀴가 나오면 swapped 덕분에 그 자리에서 멈춥니다. 가장 나쁜 경우 n(n − 1) / 2번 비교하므로 O(n²) 정렬입니다.
그림 1의 입력 칸에 다른 값을 넣고 적용을 누르면 같은 과정을 직접 따라가 볼 수 있습니다. 거꾸로 된 배열 [7, 6, 5, 4, 3, 2, 1] 을 넣어 보면 계단 그림의 21번 비교를 한 단계씩 셀 수 있습니다.
