[정렬] 버블 정렬

작성일 | In

작동 과정

버블 정렬은 인접한 두 원소를 비교해 정렬합니다.
55 07 78 12 42를 인접한 두 원소끼리 비교해 오름차순으로 정렬해보겠습니다.

1
2
3
4
5
6
7
8
9
10
11
"55 07" 78 12 42 -> swap
07 "55 78" 12 42  
07 55 "78 12" 42 -> swap
07 55 12 "78 42" -> swap
"07 55" 12 42 78  
07 "55 12" 42 78 -> swap
07 12 "55 42" 78 -> swap
"07 12" 42 55 78  
07 "12 42" 55 78  
"07 12" 42 55 78  
"07 12 42 55 78"  정렬 끝

이런 과정을 거쳐 정렬이 됩니다.
뒤쪽부터 정렬이 되어가는 것을 볼 수 있습니다.

구현

1
2
3
4
5
6
7
8
9
for(int i=0; i<n; i++){
    for(int j=0; j<n-1; j++){
        if(arr[j] > arr[j+1]){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}

커팅 방법

버블정렬은 정렬 도중에 완전히 정렬되었는데도 불구하고 계속 연산을 하는 경우가 있어서, 그 비효율적인 행동을 막아야합니다.

먼저, flag라는 변수를 만든 뒤, 바깥쪽 for문 내부 맨 위에서 1이라고 초기화를 해줍니다.
그리고 swap(교체) 행동이 일어나면 flag를 0으로 바꿉니다.
안쪽 for문이 끝났을 때 flag가 1이면 이미 완전히 정렬이 되었기 때문에 더 이상 연산을 할 필요가 없으므로 break; 를 써주시면 됩니다.

최종 코드

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0; i<n; i++){
    int flag = 1;
    for(int j=0; j<n-1; j++){
        if(arr[j] > arr[j+1]){
            flag = 0;
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
    if(flag) break;
}

복잡도 분석

버블 정렬의 시간 복잡도를 분석해봅시다.
첫 번째 for문이 n번, 두 번째 for문이 n-1번 돕니다.
n*(n-1) = n2 - n ∈ O(n2) 입니다.