선택정렬과 함께 많이 사용.
많은 비교와 적은 교환이 선택정렬의 특징이라면, 삽입정렬은 적은 비교와 많은 교환이 특징이다.
1. i=1;
2. j=i;
3. a[j-1] > a[i] 이고 j>0동안
3.1 a[j] = a[j-1] --> a[i]를 삽입할 공간을 만든다.(뒤로 옮김)
3.2 j를 하나 감소한다.
4. a[j] = a[i] --> 빈 공간에 a[i]를 삽입한다.
5. i를 하나 증가하고 2로 돌아간다.
public class InsertArray {
public int[] insertArray() {
int a[] = new int[]{12,5,1,23,44,11};
int temp =0 ;
int temp2 =0 ;
for(int i=1 ; i<a.length ; i++){
temp = a[i];
temp2 = a[i];
for(int j =i ; j >= 0 ; j--){
if(temp < a[j]){
temp2 = a[i];
a[i] =a[j];
a[j] = temp2;
i--;
}
}
}
return a;
}
public int[] insertArray2() {
long start, end;
int a[] = new int[]{12,5,1,23,44,11};
//int a[] = new int[]{12,5,1,23,44,11,1,2,3,2,1,2,45,35,2,5,22,66,44,22,88,643,23,34,63,47,26,25,36,23,135,343,463,642,666,355,333,777,222,888,100};
start= System.currentTimeMillis();
int i,j,k;
for( i=1 ; i<a.length;i++)
{
k=a[i];
for(j=i-1; (j>=0) && (k< a[j]) ; j--)
a[j+1]=a[j];
a[j+1]=k;
System.out.println("insertArray2:"+ a[0]+","+ a[1]+","+ a[2]+","+ a[3]+","+ a[4]+","+ a[5]);
}
end= System.currentTimeMillis();
System.out.println((double)(end-start)/(double)1000+"second");
return a;
}
public static void main(String[] args) {
System.out.println(insertArray());
System.out.println(insertArray2());
}
}
결과)
insertArray:5,12,1,23,44,11 (i=1)
insertArray:5,1,12,23,44,11 (i=2)
insertArray:1,5,12,23,44,11 (i=1)
insertArray:1,5,12,23,11,44 (i=5)
insertArray:1,5,12,11,23,44 (i=4)
insertArray:1,5,11,12,23,44 (i=3)
insertArray2:5,12,1,23,44,11 (i=1)
insertArray2:1,5,12,23,44,11 (i=2)
insertArray2:1,5,12,23,44,11 (i=3)
insertArray2:1,5,12,23,44,11 (i=4)
insertArray2:1,5,11,12,23,44 (i=5)
1. 이미 정렬된 배열일 경우 매우 빠른 속도를 가진다.
2. 역순의 경우 최악의 경우가 된다.
3. 난수 배열일 경우에는 선택정렬보다는 훨씬 효율이 좋다.
4. 대출 정렬된 배열의 경우 삽입정렬은 속도가 굉장히 빠르다.
--> 입력자료에 굉장히 민감하다.
내부루프 (보초)사용- 첫요소 a[0]에 값을 넣어 루프에서 비교문을 하나 없앨수있다.
항상 보초를 사용할수는 없다.
진짜 배열의 레코드들은 그대로 두고 index배열에 순서를 매겨 놓는 방식이다.
그러므로 배열의 큰 레코드들의 복사가 안이루어 지므로 속도가 빠르다.
참조 할때 a[WEBSTUDY:index(i)]이런식으로만 참조하면 된다.
그러므로 삽입정렬의 가장 큰 문제인 교환이 많다는것을 어느정도 커버가 된다.
public class IndirectArray {
public void indirectArray() {
int a[] = new int[]{12,5,1,23,44,11};
int index[] = new int[]{0,1,2,3,4,5};
//for( int i=1 ; i<a.length;i++){
// index[i] = i;
//}
int i,j,k;
for( i=1 ; i<a.length;i++)
{
k = index[i];
System.out.println("k:"+k);
//h = i;
for(j=i; (j>0) && (a[k]< a[index[j-1]]) ; j--)
index[j]=index[j-1];
index[j]=k;
System.out.println("indirectArray : "+index[0]+","+index[1]+","+index[2]+","+index[3]+","+index[4]+","+index[5]);
}
System.out.println("indirectArray values : "+a[index[0]]+","+a[index[1]]+","+a[index[2]]+","+a[index[3]]+","+a[index[4]]+","+a[index[5]]);
}
public static void main(String[] args) {
System.out.println(indirectArray());
}
}
결과)
indirectArray : 2,1,5,0,3,4
indirectArray values : 1,5,11,12,23,44