Bubble Sort(버블 정렬)
 |
| 출처 : 위키백과 |
- 시간복잡도 : O(n^2)
- 인접한 두 인자(즉, 2개씩) 비교해가며 반복하여 정렬
- 장점 : 쉬운 구현
- 단점 : 느리다.
java 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 | public class Bubble_Sort {
//난수 생성 메소드
public int[] make_rnd(int size){
//중복값 제거를 위하여 Set으로 값 관리
Set rnd = new HashSet();
int rnd_list[] = new int[size];
for(int i = 0;size>i;i++){
//1~99사이의 난수값 생성
int tmp = (int) (Math.random() * 99)+1;
rnd.add(tmp);
//중복값 생성시 다시 생성
if (rnd.size() == i + 1)
i--;
else
rnd_list[i]=tmp;
}
System.out.println("원본 배열 생성");
array_print(rnd_list, size);
return rnd_list;
}
//배열 출력 메소드
public void array_print(int rnd_list[],int size){
System.out.print("[ ");
for(int i=0;size>i;i++){
System.out.print(rnd_list[i]+ " ");
}
System.out.println("]");
}
public static void main(String args[]){
int size = 10;
Bubble_Sort sort= new Bubble_Sort();
int rnd_list[] = sort.make_rnd(size);
//버블정렬 i = 차수
for (int i = 0; size - 1 > i; i++) {
//j비교 위치
for (int j = 0; size - 1 > j; j++) {
//2개 값 비교하여 정렬
if (rnd_list[j] > rnd_list[j + 1]) {
int tmp = rnd_list[j + 1];
rnd_list[j + 1] = rnd_list[j];
rnd_list[j] = tmp;
}
}
System.out.println(i+1+"차 정렬");
sort.array_print(rnd_list, size);
}
}
}
|
원본 배열 생성
[ 89 31 19 63 55 59 97 5 61 94 ]
1차 정렬
[ 31 19 63 55 59 89 5 61 94 97 ]
2차 정렬
[ 19 31 55 59 63 5 61 89 94 97 ]
3차 정렬
[ 19 31 55 59 5 61 63 89 94 97 ]
4차 정렬
[ 19 31 55 5 59 61 63 89 94 97 ]
5차 정렬
[ 19 31 5 55 59 61 63 89 94 97 ]
6차 정렬
[ 19 5 31 55 59 61 63 89 94 97 ]
7차 정렬
[ 5 19 31 55 59 61 63 89 94 97 ]
8차 정렬
[ 5 19 31 55 59 61 63 89 94 97 ]
9차 정렬
[ 5 19 31 55 59 61 63 89 94 97 ]
댓글 없음:
댓글 쓰기