[C++] 버블정렬 (Bubble Sort)

[버블정렬]

     바로 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내준다.

(가장큰 값을 맨 뒤로 보내줌)

[문제]

1 10 5 8 7 6 4 3 2 9 를 순서대로 정렬하세요

[풀이]

#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++) { //뒤에서 부터 하나씩 줄면서 확인하기때문에 -i

if (array[j] > array[j + 1]) {

temp = array[j+1];

array[j+1] = array[j];

array[j] = temp;

}

}

}

for (i = 0; i < 10; i++) {

printf("%d", array[i]);

}

}

[문제점]

첫번째 확인할때 10번 확인 1~10

두번째는 9번 확인 2~10

....

1 번 확인

등챠수열 -> n * (n+1) / 2  ->  o(n*n)  -> 10*(10+1)/2 =55

10개를 정렬하기 위해서 55번의  확인이 필요함

선택정렬보다 효율성이 떨어진다. 그 이유는 옆에있는 원소랑 자리를 매번 바꿔줘야 하기 때문이다.