[정렬] Bubble Sort

버블소트는 인접한 두 원소를 비교하여 정렬하는 알고리즘이다.

예를 들어, 다음과 같은 배열을 오름차순 정렬하는 경우를 생각해보자.

3

1

4

2

5

우선, 첫 번째에 위치한 3과 1을 비교해 3이 1보다 크므로 위치를 바꾼다.

1

3

4

2

5

다음, 두 번째에 위치한 3과 4를 비교해 3이 4보다 작으므로 위치는 그대로이다.

따라서 세 번째에 위치한 4와 2를 비교해 4가 2보다 크므로 위치를 바꾼다.

3

1

2

4

5

마지막으로 네 번째에 위치한 4와 5을 비교해 위치가 그대로이므로 첫 번째 단계를 종료한다.

결론적으로, 가장 큰 숫자를 맨 뒤로 옮기는 과정으로 볼 수 있다.

 

두 번째 루프를 돌면 다음과 같다.

1

3

2

4

5

세 번째 루프를 돌면 다음과 같다. 네 번째도 동일하다.

1

2

3

4

5

따라서 시간복잡도는 O(n^2)이 걸린다.

---

#include <iostream>

using namespace std;

int main(void){
    int n = 10;
    int arr[10] = {2, 1, 9, 3, 4, 7, 2, 8, 10, 5};

    while(n--){
        for(int i = 0; i < n; i++){
            if(arr[i] > arr[i+1]){
                int tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
            }
        }
    }

    for(int i = 0; i < 10; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}