코딩맥스

C로 보는 버블 정렬: 한 줄씩 따라가는 동작 원리

코딩맥스수정 읽는 데 25분algorithmsortingbubble-sortc
FIG 1 · TRACE · C · bubble_sort.c
1 / 34
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번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
  • 비교 중
  • 방금 교환
  • 자리 확정
모든 단계 보기
  1. L21번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
  2. L5a[0] = 5 와 a[1] = 1 를 비교합니다. 앞이 더 크니 바꿉니다.
  3. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  4. L5a[1] = 5 와 a[2] = 4 를 비교합니다. 앞이 더 크니 바꿉니다.
  5. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  6. L5a[2] = 5 와 a[3] = 2 를 비교합니다. 앞이 더 크니 바꿉니다.
  7. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  8. L5a[3] = 5 와 a[4] = 8 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  9. L5a[4] = 8 와 a[5] = 3 를 비교합니다. 앞이 더 크니 바꿉니다.
  10. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  11. L5a[5] = 8 와 a[6] = 6 를 비교합니다. 앞이 더 크니 바꿉니다.
  12. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  13. L12바퀴가 끝났습니다. a[6] = 8 은 자리가 확정됐습니다.
  14. L22번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
  15. L5a[0] = 1 와 a[1] = 4 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  16. L5a[1] = 4 와 a[2] = 2 를 비교합니다. 앞이 더 크니 바꿉니다.
  17. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  18. L5a[2] = 4 와 a[3] = 5 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  19. L5a[3] = 5 와 a[4] = 3 를 비교합니다. 앞이 더 크니 바꿉니다.
  20. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  21. L5a[4] = 5 와 a[5] = 6 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  22. L12바퀴가 끝났습니다. a[5] = 6 은 자리가 확정됐습니다.
  23. L23번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
  24. L5a[0] = 1 와 a[1] = 2 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  25. L5a[1] = 2 와 a[2] = 4 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  26. L5a[2] = 4 와 a[3] = 3 를 비교합니다. 앞이 더 크니 바꿉니다.
  27. L6임시 변수 t를 거쳐 두 값을 바꿨습니다. swapped = 1.
  28. L5a[3] = 4 와 a[4] = 5 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  29. L12바퀴가 끝났습니다. a[4] = 5 은 자리가 확정됐습니다.
  30. L24번째 바퀴를 시작합니다. 아직 교환한 적이 없습니다.
  31. L5a[0] = 1 와 a[1] = 2 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  32. L5a[1] = 2 와 a[2] = 3 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  33. L5a[2] = 3 와 a[3] = 4 를 비교합니다. 순서가 맞으니 그대로 둡니다.
  34. L12이번 바퀴에서 한 번도 바꾸지 않았습니다. 이미 정렬되었으니 멈춥니다.
그림 1. 값 7개가 4바퀴 만에 정렬된다. 바퀴가 끝날 때마다 남은 값 중 가장 큰 값이 오른쪽 끝에 자리를 잡는다.
목차

버블 정렬은 이웃한 두 칸을 비교해서 순서가 틀리면 바꾸고, 이 일을 배열이 정렬될 때까지 되풀이합니다. 위 그림은 [5, 1, 4, 2, 8, 3, 6] 을 이 코드로 정렬하는 과정입니다. 다음 버튼을 누를 때마다 실행 중인 줄, 변수 i · j · swapped, 배열이 함께 바뀝니다. 이 입력은 4바퀴째에 멈춥니다.

한 바퀴가 하는 일

바깥 for 문이 한 번 도는 것을 한 바퀴라고 부르겠습니다. 한 바퀴 동안 안쪽 for 문이 j 를 0부터 하나씩 늘리며 a[j] 와 a[j + 1] 을 비교합니다. 앞의 값이 더 크면 임시 변수 t 에 잠깐 옮겨 두고 두 값을 맞바꾼 뒤 swapped 를 1로 바꿉니다.

FIG 2 · STEP · 1바퀴
1 / 7
51428361542836교환1452836교환1425836교환1425836그대로1425386교환1425368교환a[0]a[1]a[2]a[3]a[4]a[5]a[6]

1바퀴를 시작합니다. j = 0부터 이웃한 두 칸을 차례로 비교합니다.

모든 단계 보기
  1. 1바퀴를 시작합니다. j = 0부터 이웃한 두 칸을 차례로 비교합니다.
  2. j = 0: 5가 1보다 커서 두 값을 바꿉니다.
  3. j = 1: 5가 4보다 커서 두 값을 바꿉니다.
  4. j = 2: 5가 2보다 커서 두 값을 바꿉니다.
  5. j = 3: 5는 8보다 작아서 그대로 둡니다.
  6. j = 4: 8이 3보다 커서 두 값을 바꿉니다.
  7. j = 5: 8이 6보다 커서 두 값을 바꿉니다. 8이 a[6]에 자리를 잡고 1바퀴가 끝납니다.
그림 2. 1바퀴에서 비교는 6번, 교환은 5번이다. 5는 a[3]에서 8에 막혀 멈추고, 그다음부터는 8이 끝까지 밀려간다.

1바퀴에서 5는 1, 4, 2를 차례로 지나 a[3] 까지 갑니다. 거기서 더 큰 8을 만나 멈추고, 그 뒤로는 8이 3과 6을 넘어 맨 끝에 닿습니다. 비교 6번 중 교환이 5번입니다.

가장 큰 값이 끝에 모이는 이유

한 바퀴 동안 가장 큰 값을 만나면, 그 값은 오른쪽 이웃보다 작을 수 없습니다. 이웃보다 크면 바꾸어 한 칸 오른쪽으로 갑니다. 이웃이 같은 값이면 그대로 두지만, 비교는 그 같은 값으로 이어지므로 결과는 같습니다. 어느 쪽이든 가장 큰 값은 비교가 진행되는 방향을 따라 오른쪽으로 계속 밀려갑니다.

FIG 3 · LOOP
1425368a[0]a[1]a[2]a[3]a[4]a[5]a[6]
그림 3. 1바퀴의 j = 4, 5 두 비교에서 8은 3, 6과 차례로 자리를 바꿔 a[4]에서 a[6]까지 간다.

그래서 바퀴가 끝나면 정렬되지 않은 구간의 가장 큰 값이 그 구간의 맨 끝에 놓입니다. 끝에 놓인 값은 이후 바퀴에서 다시 움직이지 않습니다. 안쪽 for 문의 조건이 j < n - 1 - i 인 것도 이 때문입니다. 바퀴마다 확정된 칸을 하나씩 빼고 비교하니 비교 횟수가 하나씩 줄어듭니다.

바퀴는 많아야 n − 1번

한 바퀴가 끝날 때마다 값 하나가 제자리를 찾습니다. 값 n개 중 n − 1개가 자리를 잡으면 남은 하나는 저절로 맨 앞에 있습니다. 그래서 바깥 for 문은 i < n - 1 까지만 돕니다. 값이 7개면 많아야 6바퀴입니다.

FIG 4 · REVEAL
시작51428361바퀴교환 514253682바퀴교환 212435683바퀴교환 112345684바퀴교환 0 · 멈춤1234568
그림 4. 기본 입력은 바퀴마다 오른쪽 끝부터 한 칸씩 자리가 확정되고, 비교 18번과 교환 8번 끝에 4바퀴에서 멈춘다.

기본 입력에서 비교 횟수는 6, 5, 4, 3으로 바퀴마다 하나씩 줄고, 교환은 5, 2, 1, 0번입니다. 모두 합하면 비교 18번, 교환 8번입니다.

swapped로 일찍 멈추기

어떤 바퀴에서 한 번도 바꾸지 않았다면, 이웃한 값이 모두 순서대로 놓여 있다는 뜻입니다. 배열이 이미 정렬된 것입니다. 12번 줄의 if (!swapped) break; 가 이때 바깥 반복을 끝냅니다.

위 그림을 다시 보면 기본 입력은 3바퀴가 끝났을 때 이미 정렬되어 있습니다. 그래도 코드는 그 사실을 바로 알지 못합니다. 4바퀴에서 3번 비교해 보고 교환이 없다는 것을 확인한 뒤에야 멈춥니다.

FIG 5 · STATIC
1234567비교 6번, 교환 0번 → swapped = 0, break
그림 5. 이미 정렬된 값 7개는 1바퀴에서 6번 비교하고, 교환이 없으므로 바로 멈춘다.

이미 정렬된 입력이 가장 좋은 경우입니다. 첫 바퀴에서 n − 1번 비교하고 끝납니다.

비교 횟수와 시간 복잡도

가장 나쁜 경우는 거꾸로 정렬된 입력입니다. 비교할 때마다 바꾸게 되니 swapped 가 0이 되는 바퀴가 없고, n − 1바퀴를 모두 돕니다. 비교 횟수는 (n − 1) + (n − 2) + … + 1 = n(n − 1) / 2 입니다.

FIG 6 · STATIC
1바퀴62바퀴53바퀴44바퀴35바퀴26바퀴16 + 5 + 4 + 3 + 2 + 1 = 21 = 7 × 6 / 2
그림 6. 거꾸로 된 값 7개는 바퀴마다 비교가 하나씩 줄어 6 + 5 + … + 1 = 21번 비교한다.
FIG 7 · TABLE
입력바퀴비교교환
1, 2, 3, 4, 5, 6, 7 (정렬됨)160
5, 1, 4, 2, 8, 3, 6 (기본 입력)4188
7, 6, 5, 4, 3, 2, 1 (거꾸로)62121
그림 7. 값이 7개일 때 정렬된 입력은 6번, 거꾸로 된 입력은 21번 비교한다.

비교 횟수 n(n − 1) / 2 는 n² 에 비례해 늘어납니다. 그래서 가장 나쁜 경우와 평균적인 경우의 시간 복잡도는 O(n²) 입니다. 가장 좋은 경우는 비교 n − 1번이면 끝나므로 O(n) 입니다.

안정 정렬이고 제자리 정렬이다

5번 줄은 앞의 값이 뒤의 값보다 클 때만 바꿉니다. 같은 값끼리는 바꾸지 않으므로, 같은 값이 처음에 놓여 있던 순서가 정렬 뒤에도 그대로 남습니다. 이런 정렬을 안정 정렬이라고 합니다.

FIG 8 · STATIC
정렬 전정렬 후3앞13뒤2123앞3뒤
그림 8. 같은 값 3 두 개는 정렬한 뒤에도 앞의 3이 뒤의 3보다 앞에 있다.

값을 배열 안에서 맞바꾸기만 하므로 추가로 쓰는 메모리는 변수 t, i, j, swapped 뿐입니다. 입력이 커져도 추가 메모리는 늘지 않으니 제자리 정렬이기도 합니다.

다시 정리하면

버블 정렬은 이웃한 두 칸만 보고 바꾸는 단순한 규칙으로, 바퀴마다 남은 값 중 가장 큰 값을 끝으로 보냅니다. 바퀴는 많아야 n − 1번이고, 교환이 없는 바퀴가 나오면 swapped 덕분에 그 자리에서 멈춥니다. 가장 나쁜 경우 n(n − 1) / 2번 비교하므로 O(n²) 정렬입니다.

그림 1의 입력 칸에 다른 값을 넣고 적용을 누르면 같은 과정을 직접 따라가 볼 수 있습니다. 거꾸로 된 배열 [7, 6, 5, 4, 3, 2, 1] 을 넣어 보면 계단 그림의 21번 비교를 한 단계씩 셀 수 있습니다.