[Algorithm] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

• 배열에서 가장 큰 값을 찾아서 마지막에 배치시키고, 다음으로 큰 값을 찾아서 끝에서 두 번째에 배치시키고, 다음으로 큰 값을 찾아서 끝에서 세 번째에 배치시키면서 정렬해 나가는 방식
• 거품 모양과 같아서 버블 정렬(Bubble Sort)이라고 한다.

버블 정렬의 예

 

구현

$O(n^{2})$ 으로 구현하기

#include <iostream>
using namespace std;

#define N 5

int main() {
    int a[N] = { 7, 6, 9, 5, 8 };
    int tmp;
    
    for (int i = 0; i < N; i++) {   // i : Pass
        for (int j = 0; j < N - i; j++) {
            if (a[j] > a[j + 1]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        cout << a[i] << " ";
    }
        
    return 0;
}

5 6 7 8 9

 

$O(n)$ 으로 구현하기

• 버블 정렬을 진행하다 보면, 특정 회차에서 정렬이 완료되었음에도 불구하고 마지막 회차까지 비교 연산을 진행하는 경우가 있다.
• 이를 개선하기 위해 중간 회차에서 데이터의 Swap 과정이 진행되지 않으면, 정렬이 완료된 것을 의미하므로, 연산을 종료하도록 하는 코드를 넣어주면 된다.

#include <iostream>
using namespace std;

#define N 5

int main() {
    int a[N] = { 7, 6, 9, 5, 8 };
    int tmp;
    bool isSwaped;
    
    for (int i = 0; i < N; i++) {   // i : Pass
        isSwaped = false;
        
        for (int j = 0; j < N - i; j++) {
            if (a[j] > a[j + 1]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                
                isSwaped = true;
            }
        }
        
        // Swap이 한번도 수행되지 않았다면 정렬이 수행된 것이므로 연산을 종료한다.
        if (!isSwaped) {
            break;
        }
    }
    
    for (int i = 0; i < N; i++) {
        cout << a[i] << " ";
    }
        
    return 0;
}

5 6 7 8 9