삽입정렬(InsertionSort)

최악의 경우 버블정렬과 같이 n^2  의 시간복잡도를 가진다.  최선의 경우 정렬되어 있는 경우 n의 시간복잡도를 가진다. 평균 버블정렬보다 절반정도의 빠름을 보여준다.  특정위치에(인덱스)있는 요소를 적절한 위치에 들어갈 수 있도록 되어있다.  해당 인덱스는 버블정렬과 다르게, 선택되어진 특정 값이 자신의 위치를 찾는순간 더 이상 앞의 데이터와 비교할 필요(정확히 스위칭)가 없어지기 때문에 효과적이다.

 

예  제

Ex) 5 3 6 4

 

  1) 2번째 3이 선택되어 진 값

     ㅁ 5 6 4 <-- 선택된 3이 5보다 작으므로 5의 값을 오른쪽으로 한칸 스위치

      3 5 6 4 <-- 더 이상 비교 할 값이 없으므로 3은 맨 앞에 위치한다.

 

  2) 3번째 6이 선택되어 진 값

     3 5 6 4 <-- 선택된 6이 5보다 크기때문에 변동없음.

     3 5 6 4 <-- 선택된 6이 3보다 크기때문에 변동없음.

 

  3) 4번째 4가 선택되어 진 값

     3 5 ㅁ 6 <-- 선택된 4가 6보다 작으므로 6을 오른쪽으로 한칸 스위치

     3 ㅁ 5 6 <-- 선택된 4가 5보다 작으므로 5를 오른쪽으로 한칸 스위치

     3 4 5 6 <-- 선택된 4가 3보다 크기때문에 4를 2번째에 위치시킨다.

 

  결과 : 3 4 5 6

 

 

소  스

public class InsertionSort {
 
    public static void main(String[] args) {
        int[] targetArr = {3,9,6,5,2,7,4,1,8}; 
        
        int length = targetArr.length;
        
        int temp=0;
        for(int i=1; i < length; i++) {
            for(int j=i; j > 0; j--) {
                if(targetArr[j-1] > targetArr[j]) {
                    temp = targetArr[j];
                    targetArr[j] = targetArr[j-1];
                    targetArr[j-1] = temp;
                }
            }
        }
        
        for(int result : targetArr) {
            System.out.print(result);
        }
 
    }
}