005. 거품 정렬(Bubble Sort)

1. 알고리즘 설명

성능이 가장 안 좋은 정렬방법이다.
제일 왼쪽의 (0,1) 2개를 비교를 해서 큰 수가 오른쪽으로 가게하고, 그다음 (1,2)에 대해서 비교 후 교환하고 하는 작업을 (n-2, n-1)까지 반복해서 작업한다. 이렇게 하면 n-1 번 째에 가장 큰 값이 들어가게 되고, 그다음에 다시 (0,1)부터 (n-3, n-2)까지 비교하는 작업을 해서 n-2 번 째를 결정하고, 이러한 과정을 반복해서 정렬하는 것이다.

아래 애니메이션은 거품 정렬에 의해 수가 정렬되는 모습이다.(출처: wekipedia)

 

 

2. 알고리즘 Flow

1. i=n-1
2. i=0이면 끝낸다.
3. j=0
4. j=i가 되면 7로 간다.
5. if(v[j] > v[j+1])이 두 수를 바꾼다.
6. ++j하고 4로 간다.
7. --i하고 2로 간다.

 

3. 소스 코드

void bubbleSort(vector<int> &v){
  int size = v.size(); 
  for(int i=size-1;i>0;--i){
    for(int j=0;j<i;++j){
      if(v[j] > v[j+1]) swap(v[j], v[j+1]);    
    }          
  }  
}

 

4. 시간 복잡도: O(n²)

• 비교: O(n²)

• 교환: O(n²)

i=n-1 : 비교(최소 n-1, 최대 n-1), 교환(최소 0, 최대 n-1)
i=n-2 : 비교(최소 n-2, 최대 n-2), 교환(최소 0, 최대 n-2)
...
i=1   : 비교(최소 1, 최대 1), 교환(최소 0, 최대 1)

총 비교: 최소 n^2/2, 최대 n^2/2
총 교환: 최소 0    , 최대 n^2/2

 

5. 공간 복잡도: O(n)

 

 

6. 데이터 안정성: 안정적이다.

(같은 값에 대해서 정렬 후에도 그 순서가 보존된다.)

 

 

7. 알고리즘 특징

비교도 O(n²) 교환도 O(n²)으로 최악의 성능을 보이는 정렬 알고리즘이다. 따라서, 현실에서 사용되지 않는다.

 

-끝-