[정렬] 버블 정렬

0. 핵심 아이디어

• 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까?

---

1. 예시

1. 1  10  5  8  7  6  4  3  2  9
2. 1  5  10  8  7  6  4  3  2  9
3. 1  5   8  10 7  6  4  3  2  9
4. 1  5   8  7  10 6  4  3  2  9
5. 1  5   8  7  6  10 4  3  2  9
6. 1  5   8  7  6   4 10 3  2  9
7. 1  5   8  7  6   4  3 10 2  9
8. 1  5   8  7  6   4  3  2 10 9
9. 1  5   8  7  6   4  3  2  9  10    //결국 가장 큰 값이 뒤로 오게 됨. 첫번째 Loop 끝.
10. 1  5   7  8  6   4  3  2  9  10
11. 1  5   7  6  8   4  3  2  9  10
12. ....

---

2. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int i, j, temp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i = 0; i < 10; i++){
        for(j = 0; j < 9 - i; j++){
            if(array[j] > array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
    for(i = 0; i < 10; i++){
        cout << array[i] << " ";
    }
    return 0;
}
 

---

3. 시간복잡도

• N * (N+1) / 2 => O(N^2)
• 선택 정렬보다 느리다. 왜냐하면 버블 정렬은 계속해서 자리를 바꾸는 연산을 실시하기 때문에 작업량이 더 많다. 선택 정렬은 마지막에만 교체하지만 버블 정렬은 매번 교체한다.