2. 버블 정렬

< 버블 정렬 >

 

■ 버블 정렬 : 옆에 있는 값과 비교하여 더 작은 값을 앞으로 보내는 정렬 방법 ( 가장 효율성 ↓ )

 

( 구현하기는 가장 쉬운데 효율성이 가장 떨어짐 )

 

#include <stdio.h>
int main(void) {
	int i , j, min, temp; 
    //temp = 특정한 두 숫자를 서로 바꾸기 위해서
    
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    
    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\n", array[i]);
     }
    
    return 0;
}

 

10 + 9 + ··· + 2 + 1

= N * ( N + 1 ) / 2

= O ( N * N )

= O ( N^2)

= 시간복잡도

 

▷ 버블 정렬이 선택 정렬보다 느림.

왜? 버블 정렬은 계속해서 옆에 있는 것과 자리 바꾸는 연산 수행하기 때문.