버블정렬 (feat. 거품정렬, Bubble Sort)

 

 

거품 정렬 또는 버블 정렬( - 整列, 영어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2) 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

 

버블정렬은 두개의 값을 서로 비교하는 방식입니다.

단순하고 직관적이므로 실제로 구현에서 나도 모르게 사용하는 정렬입니다.

배열 4개가 있다고 가정해봅시다.

아래는 오름차순을 기준으로 기재하였습니다.

 

1. 배열[0]과 배열[1]을 비교하여 작은 값은 앞에, 큰값은 뒤에 배치합니다.
2. 배열[1]과 배열[2]를 비교하여 작은 값은 앞에, 큰값은 뒤에 배치합니다.
3. 배열[2]과 배열[3]를 비교하여 작은 값은 앞에, 큰값은 뒤에 배치합니다. 따라서 배열[3]은 배열 4개 중 가장 큰 값입니다.
4. 배열[0]과 배열[1]을 비교하여 작은 값은 앞에, 큰값은 뒤에 배치합니다.
5. 배열[1]과 배열[2]를 비교하여 작은 값은 앞에, 큰값은 뒤에 배치합니다. 따라서 배열[2]는 배열 4개 중 두번째로 큰 값입니다.

 

반응형

 

위와 같은 방법으로 버블정렬을 구현할 수 있습니다.

모든 배열의 값들을 비교하므로 브루트포스 알고리즘 기법이라고 할 수 있습니다.

 

버블정렬을 코드로 구현하면 아래와 같습니다.

 

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <random>
#include <algorithm>
using namespace std;
void bubble_sort(int* arr, int length){
    for(register int i = 0; i < length - 1; ++i)
        for(register int j = 0; j < length - i - 1; ++j)
            if(arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}
int main(){
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<int> range(0, 10000);
    int arr[20];
    for(auto& v : arr)
        v = range(mt);
    cout << "before : ";
    for(auto& v : arr)
        cout << v << " ";
    cout << "\n";
    bubble_sort(arr, sizeof(arr) / sizeof(arr[0]));
    cout << "after : ";
    for(auto& v : arr)
        cout << v << " ";
    return 0;
}
// *&)*@*

 

버블정렬 (위키백과)