_
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]);
}
}
}
}