자료구조 :: 버블정렬 Bubble sort (c/c++ 구현)

버블 정렬 (Bubble Sort)

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자

 

버블정렬 또한 선택정렬과 같이 비효율적인 정렬 방법중 하나다.

엄밀히 말하면, 버블정렬이 선택정렬보다 연산량이 많다고 할 수 있다.

 

#include <stdio.h>
 
int main(void){
    int array[10] = {4, 5, 2, 7, 9, 1, 8, 3, 6, 10};
    int i, j, temp;
    
    for(i=0; i<10; i++){
        for(j=0; j<9-i; j++){
            if(array[j] > array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }    
        }
    }
 
    // 결과 확인 
    for(i=0; i<10; i++){
        printf("%d ", array[i]);
    }
    return 0;
}​

 

 

결국은 가장 큰 값이 맨 마지막으로 이동하게 된다.

 

선택정렬은 가장 작은값을 골라서 나중에 한번만 값을 바꿔주지만,

버블정렬은 매번 옆에 있는 값과 바꾸기 때문에 더 많은 연산을 한다. 

 

시간복잡도는 선택정렬과 똑같다. 즉,

 

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

 

관련 글

2018/04/29 - [Algorithm/백준 온라인 저지] - 백준/2750번 :: 수 정렬하기

2018/04/28 - [Algorithm] - 자료구조 :: 선택정렬 Selection sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)