[Algorithm/C++] 버블 정렬(Bubble Sort) - 거품 정렬

 

1. 설명

 

버블 정렬(Bubble Sort)란 거품 정렬이라고도 하며 인접한 원소 간 비교하는 작업을 반복적으로 수행함으로써 정렬된 리스트를 얻는 정렬 방법 중 하나이다.

 

 

동작 예시 (출처: https://visualgo.net/en/sorting)

 

 

동작 예시를 보면 인접한 원소끼리 비교하여 왼쪽의 원소가 오른쪽의 원소보다 클 경우 위치를 교환해주고, 그다음 원소와도 이 작업을 반복하여 수행함으로써 가장 큰 원소가 가장 오른쪽으로 이동하게 된다.

 

 

이 과정을 또 반복하여 수행함으로써 가장 큰 값을 갖는 원소가 오른쪽에 차곡차곡 위치하게 되므로, 최종적으로 정렬된 리스트를 얻을 수 있게 된다.

 

 

 

특징

▶ 시간 복잡도는 O(N^2)이다. 정렬이 되어 있는 상태 이어도 각 원소끼리 비교를 수행하여야 하기 때문에 동일하다.

▶ 공간 복잡도는 O(1)이다. 추가적인 삽입, 삭제 없이 위치만 변경해주기 때문

▶ Stable Sort이다. Stable Sort란 동일한 값이 있을 경우 정렬 후 그 값들끼리 순서가 유지되는 정렬이다. 예를 들어 만약 4가 2개 있을 경우 앞쪽에 위치한 4가 정렬 후에도 앞쪽에 위치하게 되는 것이다.

▶ 시간 복잡도를 보면 O(N^2)로 비효율적이지만 단순히 비교와 교체하는 동작만 구현하면 되므로 간단하게 구현이 가능하다.

 

 

 

 

2. 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <iostream>
using namespace std;

void print(vector<int> v, string s);
void bubble_sort(vector<int> v);
void bubble_sort_reverse(vector<int> v);

int main() {
    vector<int> v = { 1, 7, 4, 3, 2, 9, 4 };
    bubble_sort(v);
    bubble_sort_reverse(v);

    return 0;
}


void print(vector<int> v, string s) {
    cout << s << " : ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}

void bubble_sort(vector<int> v) {
    int size = v.size();
    for (int i = 0; i < size; i++) {
        for (int j = 1; j < size - i; j++) {
            if (v[j] < v[j - 1]) {
                int temp = v[j];
                v[j] = v[j - 1];
                v[j - 1] = temp;
            }
        }
    }
    print(v, "Sort");
}

void bubble_sort_reverse(vector<int> v) {
    int size = v.size();
    for (int i = 0; i < size; i++) {
        for (int j = 1; j < size - i; j++) {
            if (v[j] > v[j - 1]) {
                int temp = v[j];
                v[j] = v[j - 1];
                v[j - 1] = temp;
            }
        }
    }
    print(v, "Sort Reverse");
}

 

결과

 

● print / bubble_sort / bubble_sort_reverse 이 3개의 함수를 정의하였으며 각 함수명에서 기능을 유추할 수 있듯이 출력과 오름차순 버블 정렬, 내림차순 버블 정렬 기능을 하는 함수들이다.

 

 

 

● bubble_sort 함수 부분을 살펴보면 2중 for문을 사용하여 인접한 원소끼리 비교 후 클 경우 교환하는 작업을 수행하여 가장 큰 원소는 가장 오른쪽으로 이동하게 된다.

 

여기서 내부의 for문을 살펴보면 변수 j = 1부터  size - i만큼 for문을 수행한다. 이러한 이유는 가장 오른쪽에 위치한 원소는 이미 비교와 교환 작업을 수행하여 가장 큰 원소임을 판별하였으므로 비교할 필요가 없기 때문이다.

 

따라서 외부의 for문에서 사용하는 변수 i가 의미하는 것은 이미 정렬되어 위치가 확정된 원소의 개수로도 볼 수 있다.

 

 

 

● bubble_sort_reverse 함수는 리스트를 내림차순으로 정렬하는 함수이다. 전체적인 프로세스는 bubble_sort 함수와 동일하며, 다만 인접한 원소끼리 비교 시 오른쪽에 있는 원소가 클 경우 교체 작업을 수행함으로써 결과적으로 가장 작은 원소가 오른쪽에 차곡차곡 위치하게 되어, 최종적으로 내림차순으로 정렬이 되게 된다.