[자료구조] 버블 정렬 ( bubble sort )...

[자료구조] 버블 정렬 ( bubble sort )...

버블 정렬 (bubble sort )은 인접한 두개의 원소를 비교하여 자리를 교환하는

방식으로, 첫 번째 원소부터마지막 원소까지 반복하면 가장 큰 원소가 마지막

자리에 온다. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마

지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다

고 해서 버블 정렬이라고 한다.

버블 정렬을 함수로 구현하면 다음과 같다.

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

버블 정렬에서 사용하는 메모리의 크기는 정렬할 원소의 개수 n이 된다. 버블

정렬에서 연산 시간이 가장 짧은 최선의 경우는 자료들이 이미 정렬되어있는

경우다. 이런 경우에는 i 번째 원소는 n - i 번 비교하게 되므로 비교 횟수는

n(n-1)/2가 된다. 그리고 이 경우에 원소의 자리 교환은 발생하지 않는다. 

버블 정렬에서 비교 횟수가 가장 많은 경우는 역순으로 정렬되어 있는 경우인

데 이 경우에도 i 번째 원소는 n-i번 비교하게 되므로 비교 횟수는 n(n-1)/2 이

되고, 자리 교환을 n-i번 하게 되므로 교환 횟수도 n(n-1)/2이 된다. 

버블 정렬에서 비교 횟수에 대한 시간 복잡도는 O(n²)이 된다.  

아래의 동영상을 보면.. 확실히 이해가 될 것이다..