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

버블정렬

이웃하는 숫자를 비교하여 작은 수를 앞 쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘이다.

 

버블정렬의 시간복잡도는 O(N^2)이다.

한 번의 Loop에 요소의 갯수만큼 비교를 하며 총 Loop는 요소의 개수번 돈다.

 

정렬할 수:

15, 2, 6, 27, 24, 9, 8, 13,10, 1, 5

 

실행 결과

0 회전 결과: 2 6 15 24 9 8 13 10 1 5 

1 회전 결과: 2 6 15 9 8 13 10 1 5 24 

2 회전 결과: 2 6 9 8 13 10 1 5 15 24 

3 회전 결과: 2 6 8 9 10 1 5 13 15 24 

4 회전 결과: 2 6 8 9 1 5 10 13 15 24 

5 회전 결과: 2 6 8 1 5 9 10 13 15 24 

6 회전 결과: 2 6 1 5 8 9 10 13 15 24 

7 회전 결과: 2 1 5 6 8 9 10 13 15 24 

8 회전 결과: 1 2 5 6 8 9 10 13 15 24 

9 회전 결과: 1 2 5 6 8 9 10 13 15 24 

10 회전 결과: 1 2 5 6 8 9 10 13 15 24 

11 회전 결과: 1 2 5 6 8 9 10 13 15 24 

 

소스코드:

void bubblesort(int a[], int n){
     for(int k = 0; k <= n; k++){ //k는 0부터 n(요소 개수)까지
         for (int i = 0; i < n - k; i++)  { //i는 0부터 요소개수 - k까지 1)
             if (a[i + 1] < a[i]) {
                 int tmp = a[i + 1];
                 a[i + 1] = a[i];
                 a[i] = tmp;
             }
         }
     }
}

1) i가 n - k까지인 이유는 Loop가 1회전 할 때마다 큰 수 부터 뒤에서 정렬되기 때문

 

0 회전 결과: 2 6 15 24 9 8 13 10 1 5 

1 회전 결과: 2 6 15 9 8 13 10 1 5 24 

2 회전 결과: 2 6 9 8 13 10 1 5 15 24 

1회전 결과로 까장 큰 수 24 가 정렬됨 (11 - 1 = 10 ) 10번째 위치 정렬 완료.

2 회전 결과: 2 6 9 8 13 10 1 5 15 24 

2회전 결과로 11 - 2 = 9 9번째 위치 정렬 완료