Bubble Sort ( 버블 정렬 )

** 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 ! , 오름차순으로 정렬한다.

## 개념 요약 ##

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘.
  • 인접한 2개의 값을 비교하여, 크기가 순서대로 되어있지 않으면 교환한다.
• 선택 정렬과 기본 개념이 유사하다. (SWAP)

## 구체적인 개념 ##

• 버블 정렬은 1번째 값과 2번째 값을, 2번째 값과 3번째 값을....3번째와 4번째를.... 이런식으로 (마지막-1) 번째 자료와 마지막 자료를 비교해 교환하면서 자료를 정렬한다.
• 1회전을 수행하고 나면 , 가장 큰 값이 맨 뒤로 이동하므로, 2번째 loop 에서는 맨 끝에 간 큰값은 정렬에서 제외되고, 2회전을 수행하면 끝에서 2번째 값은 다음 loop 에서 제외된다. 이렇게 1회전을 수행할 때 마다, 정렬에서 제외되는 값이 하나씩 늘어나게 된다.

## Bubble Sort 알고리즘의 특징 ##

• 장점
  • 구현이 매우 간단! 
• 단점
  • 순서에 맞지않은 요소를 인접한 요소와 교환한다.!
  • 하나의 값이 가장 왼쪽 -> 가장 오른쪽으로 이동하기 위해서는, 모든 다른 값들과 교환되야한다.
  • 특히, 특정 값이 이미 최종 위치에 있는 경우여도 교환해야함.
• 일반적으로 자료의 swap 이 자료의 move 보다 더 복잡하기 때문에, 버블 정렬은 단순성에도 거의 쓰이지 않음. 

## Bubble Sort 의 시간 복잡도 ##

• 비교 횟수
  • 최상 / 평균 / 최악 모두 일정.
  • n-1, n-2, .... 2, 1 번 = n(n-1) / 2
• 교환 횟수
  • 입력 자료가 역순으로 정렬되어있는 최악의 경우, 1번 교환하기 위해 3번의 이동(swap 동작)이 필요하므로, (비교횟수*3)번 = 3n(n-1)/2
  • 입력 자료가 이미 정렬되어 있는 경우, 자료의 이동 발생 안함. 
• T(n) = O(n^2)

#include <stdio.h>
#define MAX_SIZE 5

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

void main() {
    int i;
    int n = MAX_SIZE;
    int list[5] = {7,4,5,1,3};

    bubble_sort(list, n);

    for(i = 0; i < n; i++) {
        printf("%d, ", list[i]);
    }
}