Insertion Sort(삽입 정렬)
 |
| 출처 : 위키백과 |
- 시간복잡도 : O(n^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
53
54
55
56
| public class Insertion_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;
Insertion_Sort sort= new Insertion_Sort();
int rnd_list[] = sort.make_rnd(size);
//버블정렬 i = 차수
for (int i = 1; size > i; i++) {
//j비교 위치
for (int j = 0; i > j; j++) {
//2개 값 비교하여 정렬
if(rnd_list[j]>rnd_list[i]){
int tmp[] = new int[size];
System.arraycopy(rnd_list, 0, tmp, 0, j);
tmp[j]=rnd_list[i];
System.arraycopy(rnd_list, j, tmp, j+1, i-j);
System.arraycopy(rnd_list, i+1, tmp, i+1, size-(i+1));
rnd_list = tmp;
break;
}
}
System.out.println(i+"차 정렬");
sort.array_print(rnd_list, size);
}
}
}
|
원본 배열 생성
[ 64 95 54 82 18 69 43 7 68 29 ]
1차 정렬
[ 64 95 54 82 18 69 43 7 68 29 ]
2차 정렬
[ 54 64 95 82 18 69 43 7 68 29 ]
3차 정렬
[ 54 64 82 95 18 69 43 7 68 29 ]
4차 정렬
[ 18 54 64 82 95 69 43 7 68 29 ]
5차 정렬
[ 18 54 64 69 82 95 43 7 68 29 ]
6차 정렬
[ 18 43 54 64 69 82 95 7 68 29 ]
7차 정렬
[ 7 18 43 54 64 69 82 95 68 29 ]
8차 정렬
[ 7 18 43 54 64 68 69 82 95 29 ]
9차 정렬
[ 7 18 29 43 54 64 68 69 82 95 ]
