[ 2주차 ] Java - 버블 정렬

버블 정렬

선택정렬은 1번부터 10번까지 있다고 가정했을때,

1번을 기준으로 10번까지 순서대로 비교해 나가는거라면

버블정렬은 한칸씩 이동하며 비교를 해나간다.

1번2번 비교 후 2번3번 비교 3번4번 비교 .....

int num[] = {50, 40, 30, 20, 10};
for(int i=1; i<num.length; i++) {
	for(int j=0; j<num.length-i; j++) {
		if(num[j] > num[j+1]) {
			temp = num[j];
			num[j] = num[j+1];
			num[j+1] = temp;
		}
	}
}

i = 1 첫번째 부터 시작하여 반복문이 한번 돌게 되면 num에는 {40,30,20,10,50} 이 저장이 된다.

1회전 이후에 가장 큰 숫자는 맨 뒤로 가게 된다.

1회전 이후에는 {40,30,20,10,50}

2회전 이후에는 {30,20,10,40,50}

3회전 이후에는 {20,10,30,40,50}

4회전 이후에는 {10,20,30,40,50}

이렇게 정렬이 끝난다.

 

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