728x90
삽입 정렬을 설명할때 보통 카드 게임에서 카드를 정렬하는 방식과 같다고 말한다. 0번 인덱스와 1번 인덱스를 비교하여 정렬한다. 이후 0,1,2를 비교해서 자리를 찾는다. 그 다음은 3번 인덱스가 들어갈 자리를 찾고 이런 식으로 끝까지 비교한다. 정렬된 배열에서 지정한 자리에 자료를 삽입하여 정렬하므로 삽입 정렬이라고 부른다. 단 초기 Key값을 0번 인덱스의 값이 아닌 1번 인덱스의 값으로 지정한다.
삽입 정렬의 시간 복잡도 또한 O(n2)로 버블,선택 정렬과 동일하다.
이 과정을 자바 코드로 표현하면 아래와 같다.
public class insert {
public static void insertSort(int[] a){
int N = a.length;
int key;
int i,j;
for (i = 1; i <= N-1; i++) {
key = a[i];//key값은 1번째 인덱스부터 시작한다.
for (j = i-1; j >=0; j--) {
if(a[j] > key) {
a[j + 1] = a[j];//a[j]에 있던 값을 한 칸 뒤로 민다.
}
else
break;
}
a[j+1] = key;//key값의 자리를 찾아서 삽입한다
}
}
public static void main(String[] args) {
int[] a= {8,31,48,73,3,65,20,29,11,15};
insertSort(a);
for(int i:a){
System.out.printf("%d ",i);
}
}
}
선택 정렬, 버블 정렬과 동일한 조건의 실험을 진행한다.
실험 결과 0.026초가 나와서 버블 정렬 < 선택 정렬 < 삽입 정렬 순으로 빠름을 알 수 있다.
728x90
