Bubble Sort

Bubble Sort

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

• 최선, 평균, 최악의 시간복잡도가 모두 O(n^2)로 느린 정렬 기법이지만, 코드가 직관적이고 간단하다.
• in-place 기법이기 때문에 공간복잡도는 O(n)이다.
• 정렬시에 동등한 원소에 대하여 정렬 전과 후의 순서가 일치함을 보장하는 Stable Sort 이다.
• i번째 라운드에, 첫번 째 원소부터 N-i 번째 원소까지 순서대로 비교하면서, 제일 큰 원소를 찾아 N-i 에 위치시킨다.
• 평균 시간 복잡도 O(n^2)인 삽입, 선택 정렬에 비해 swap 연산이 비교적 많이 발생한다.