_

1. 소개

\(O(n^2)\)정렬 중에서 구현이 제일 쉽고 유명한 방법이다. 인접한 두개의 항의 대소를 비교하여 작은 것을 앞으로 보내는 방법이다.

이 방법의 정당성은 이해하기 쉽다. (1, 2), (2, 3), … ,(n-1, n) 번을 순차적으로 비교하여 swap을 하면, 다른 원소들의 상태는 모르지만 n번째 원소의 값이 최대라는 것은 확신할 수 있다. 이를 n번 반복하여 뒤에서부터 올바르게 숫자를 채워나간다면 정렬이 완료될 것이다. 이를 for문 두개를 이용하여 구현할 수 있고, 총 연산이 \(n*(n-1)/2\)번 실행되므로 시간복잡도는 \(O(n^2)\)이다.

2. 코드

void Bubble_Sort(){
    for(int i=1; i<N; i++){
        for(int j=1; j<=N-i; j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j], arr[j+1]);
            }
        }
    }
}