[알고리즘] 버블정렬 (Bubble Sort)

 

버블 정렬은 알고리즘이 데이터를 정렬하는 과정이

물속에서 일어난 거품이 위로 올라오는 모습과 같다고 해서 붙혀졌다.

 

실제로 데이터가 뜨거나 하지는 않지만

간단하고 손쉽게 할 수 있는 정렬이다.

 

버블정렬은 데이터들을 순회하면서(곳곳히 돌면서) 교환을 통해서 정렬을 한다.

 

다음을 보자.

5

1

6

4

2

3

1부터 6까지 무작위로 저장된 배열이 있다고 해보자

 

이때 버블 정렬을 이용해 오름차순으로 정렬 해보자.

5

1

6

4

2

3

먼저 5와 1을 비교했을 때 5가 1보다 큰 수이므로 서로 위치 교환을 해준다.

 

1

5

6

4

2

3

1과 5의 위치를 바꾼 뒤 5와 6을 비교해보자.

5는 6보다 작으므로 이동의 변화가 없다.

그러므로 비교대상을 다음으로 넘어간다.

 

1

5

6

4

2

3

비교 대상을 넘어가서 6과 4를 서로 비교해 보자.

6은 4보다 큰 수이므로 서로 위치 교환을 해준다.

 

1

5

4

6

2

3

이제 6과 2의 비교를 해보자

6은 2보다 큰 수이므로 서로 위치 교환을 해준다.

 

1

5

4

2

6

3

이제 마지막까지 왔다

6은 3보다 큰 수 이므로 서로 위치 교환을 해준다.

 

1

5

4

2

3

6

6은 이제 제 자리를 찾았다.

이제 6을 제외한 나머지 부분끼리 비교를 하면 된다.

 

같은 내용의 반복이므로 바뀌는 모습의 그림만 봐도 이해가 될 것이다.

1

5

4

2

3

6

 

1

5

4

2

3

6

 

1

4

5

2

3

6

 

1

4

2

5

3

6

 

1

4

2

3

5

6

 

1

4

2

3

5

6

 

1

4

2

3

5

6

 

1

2

4

3

5

6

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

복사&붙여넣기 신공으로 다 하긴 했는데 …

아 ……

 

 

아무튼 .. 결론부터 이야기 하자면

버블정렬의 속도는 느리다.

 

얼마나 느린지 계산을 해보자.

일단 정렬하고자 하는 데이터 수가 n 이라고 할 때 n-1만큼 반복하면 정렬이 끝이 난다.

고등학교때 배운 기억도 안나는 수열을 떠올려 보면 …

 

• 버블정렬의 비교 횟수 = (n-1) + (n-2) + (n-3) + … + (n-(n-2))+(n-(n-1))

먼저 (n-(n-1)) = (n-n+1) = +1 이므로..

위의 식을 조금 변경 시켜보면 ..

(n-1) + (n-2) + (n-3) + … + (n-(n-2))+(n-(n-1))

= (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1

 

다음은 버블정렬을 구현한 간단한 예제 소스코드이다.

main.cpp

#include <iostream>   static const int ARRAY_MIN = 0; static const int ARRAY_MAX = 10;   void PrintData( int *Data ); void BubbleSort( int *Data );   int main( ) {     int nData[ARRAY_MAX] = { 5,10,1,3,9,8,6,7,2,4 };       PrintData( nData );    //정렬하기 전 데이터          BubbleSort( nData );       std::cout<<"버블정렬 완료"<<std::endl;       PrintData( nData );    //정렬하기 전 데이터       return 0; }   void PrintData( int *Data ) {     for( int nCount = ARRAY_MIN ; nCount < ARRAY_MAX ; ++nCount )     {         std::cout<<nCount<<"번째 데이터 : "<<Data[nCount]<<std::endl;     } }   void BubbleSort( int *Data ) {     for( int nCount1 = ARRAY_MIN ; ARRAY_MAX > nCount1 ; ++nCount1 )     {         for( int nCount2 = ARRAY_MIN ; ( ARRAY_MAX - (nCount1+1) ) > nCount2 ; ++nCount2 )         {             if( Data[ nCount2 ] > Data[ (nCount2)+1 ] )             {                 int nTemp = Data[ (nCount2)+1 ];                 Data[ (nCount2)+1 ] = Data[ nCount2 ];                 Data[ nCount2 ] = nTemp;             }         }     } }

 

출력결과