| (N-1)+(N-2)……2+1 = n^2 최악, 최선, 평균에 상관없이 항상 n^2 만큼의 시간복잡도를 가진다. 가장 왼쪽수 부터, 바로 옆에 있는 값과 비교하여 정렬을 한다. |
예 제
Ex) 4 1 3 2
1) 가장 좌측에 있는 4부터 값을 비교 한다.
1 4 3 2 <-- 4, 1 값 비교하여 4의 값이 더 크므로 값을 스위치
1 3 4 2 <-- 4, 3 값 비교하여 4의 값이 더 크므로 값을 스위치
1 3 2 4 <-- 4, 2 값 비교하여 4의 값이 더 크므로 값을 스위치
2) 1)에서 가장 큰수인 4를 확정 지었으므로 -1개수만큼만 비교한다.
1 2 3 <-- 2, 3 값 비교하여 3의 값이 더크므로 값을 스위치
3) 2)에서 가장큰수인 3을 확정 지었으므로 -1개수만큼만 비교한다.
1 2 <-- 1, 2 값 비교하여 1이 2보다 작으므로 그대로 둔다.
결과 : 1 2 3 4
소스
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class BubbleSort {
public static void main(String[] args) {
int[] targetArr = {3,9,6,5,2,7,4,1,8};
int length = targetArr.length;
for(int i=length-1; i > 0; i--) {
for(int j=0; j < i; j++) {
if(targetArr[j] > targetArr[j+1]) {
int temp = targetArr[j];
targetArr[j] = targetArr[j+1];
targetArr[j+1] = temp;
}
}
}
for(int result : targetArr) {
System.out.print(result);
}
}
}
|
결과
