[C언어] 버블정렬

버블정렬

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오.
1 10 5 8 7 6 4 3 2 9

버블정렬 : 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내기

첫번째 수행 시 가장 큰 값인 10이 맨 마지막으로 가게 되는 구조
1. 1 10
2. 1 5 10
3. 1 5 8 10
4. 1 5 8 7 10
5. 1 5 8 7 6 10
6. 1 5 8 7 6 4 10
7. 1 5 8 7 6 4 3 10
8. 1 5 8 7 6 4 3 2 10
9. 1 5 8 7 6 4 3 2 9 10 

 

#include

<stdio.h>


int main(void){
	int i, j, 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 ", array[i]);
    }
	
    return  0;
}

 

시간복잡도

N이 아주 크다고 가정할 때
O(N * N)
=> 시간복잡도는 선택정렬과 같지만 버블정렬이 더 비효율적이다.