[Sort] Bubble Sort

- 일반적으로 버블 정렬보다 삽입 정렬의 복잡도가 더 좋다고 함.

 

- 유일한 장점/사용 이유? 는 입력 목록이 이미 정렬되어 있는지를 탐지할 수 있다는 점

 

- 시간 복잡도

    Worst: O(n^2)

    Best: O(n)   --> 이미 정렬되어 있는 경우.

    Average: O(n^2)

 

- 공간 복잡도: O(1)

 

- 개선된 Bubble 정렬 코드

  --> Swap 하는 부분에 flag 변수를 넣어서 한 바퀴 도는 동안 flag 변수가 바뀌지 않았다면

       이미 정렬이 완료된 것이기에 Loop를 끝낸다.

 

void bubble_sort_advanced(int data[], int n) {
    int i, j;
    int temp;
    int flag = 1;
 
    for (i = n - 1; flag&&i >= 1; i--) {
        flag = 0;
        for(j=0; j<i; j++)
            if (data[j] > data[j + 1]) {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
                flag = 1;
            }
    }
}