[바람이] Bubble Sort

* Bubble Sort

마치 거품방울이 뽀글뽀글 올라가는 모양과 비슷하다하여 붙어진 이름이다.
Bubble Sort는 두가지만 알고 있으면 된다.

1. 두가지 값을 비교
2. 두값을 swap함

백문이 불여일견이다.

// Bubble sort
void bubble_sort(int size , int* val)
{
     for (int i = 0 ; i < size - 1; i++)
    {
          for (int j = 0 ; j < size - 1 - i ; j++)
         {
              if (val[j] > val[j+1])
              {
                    int tmp = val[j];
                    val[j] = val[j+1];
                    val[j+1] = tmp;
              } 
         }
   }
}

예로 다음 배열을 Bubble Sort 해보이겠다.
{ 9 , 7 , 3 , 5 , 1 , 7 , 2 }

우선 첫 Loop에서의 모습을 보이겠다.
9 7 3 5 1 7 2
7 9 3 5 1 7 2
7 3 9 5 1 7 2
7 3 5 9 1 7 2
7 3 5 1 9 7 2
7 3 5 1 7 9 2
7 3 5 1 7 2 9

마치 왼쪽이 밑이고 오른쪽이 위라고 생각하면 9라는 값은 마치 거품방울이 올라가듯
뽀글뽀글 올라가는 것이 보인다 @^-^@

다음은 7 값이 올라가게 될것이다.

결국  1 2 3 5 7 7 9 로 정렬이 될 것이다.



* 장점
  1. 알고리즘이 간단하다.
2. 2중 Sorting이 간편하다. 즉, 학번순으로 정렬을 한뒤 같은 학번내에서 이름순의 정렬이
     가능해진다.

* 단점
  1. 성능이 O(n^2)으로 약간 느리다고 할 수 있다.