[Algorithm/Java] 삽입 정렬 (insertion sort)

삽입 정렬 (insertion sort)

삽입정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.

평균 시간복잡도는 O(n^2)으로 느리지만, 구현하기 쉽다.

---

핵심 이론

정렬 대상(선택 값)을 현재 정렬된 데이터 범위 내에서 삽입할 위치를 찾는 것이 삽입 정렬의 핵심이다.

 

예제

첫 번째 데이터는 이미 정렬된 데이터이므로 넘어가고 두 번째 데이터부터 시작한다.

 

(사이클 1)

1. 두 번째 데이터 32를 선택하고, 정렬된 데이터 범위(0-1번 인덱스) 내에서 삽입할 위치를 찾는다. (0번 인덱스)
2. 정렬된 위치 중 삽입할 자리를 만들기 위해 정렬범위 중 삽입할 자리의 오른쪽 데이터들을 옆으로 한 칸씩 이동시킨다.
3. 따로 저장해 둔 선택 데이터를 삽입위치에 삽입한다.

(사이클 2)

1. 세 번째 데이터 24를 선택하고, 정렬된 데이터 범위(0-2번 인덱스) 내에서 삽입할 위치를 찾는다. (0번 인덱스)
2. 삽입할 자리를 비운다.
3. 삽입한다.

(사이클 3)

네 번째 데이터 60을 선택하였으나, 정렬된 데이터 범위(0-3번 인덱스)에서 60은 이미 정렬된 것과 다름없으므로 넘어간다.

 

(사이클 4)

1. 다섯 번째 데이터 40을 선택하고, 정렬된 데이터 범위(0-4번 인덱스) 내에서 삽입할 위치를 찾는다. (3번 인덱스)
2. 삽입할 자리를 비운다.
3. 삽입한다.

---

Code 예제 1

	int[] arr = new int[n]; //arr = [ 42 32 24 60 40 ] 
    
	//삽입 정렬
        for(int i=1; i<n; i++){
            int ins_point = i;
            int ins_value = arr[i]; // 선택 값은 따로 저장해 둔다.
            
            //j=i-1부터 0까지 돌면서 삽입 위치 찾기
            for(int j=i-1;j>=0;j--){
                if(arr[j]<ins_value){
                    ins_point = j+1;
                    break; //삽입 위치 찾으면 break
                }
                if(j==0){
                    ins_point=0;
                }
            }
            
            //삽입을 위해 삽입 위치에서 i까지의 데이터를 오른쪽으로 한칸씩 밀기
            for(int j=i;j>ins_point;j--){
                arr[j] = arr[j-1];
            }
            
            //삽입 위치에 선택 값 넣기
            arr[ins_point] = ins_value;
        }

---

Code 예제 2

조금 더 간단한 방법이다.

위에서는 이번에 선택한 값을 저장해두고, 해당값보다 작은 값을 찾은다음에 그 왼쪽 자리에 값을 넣기위해

이번에 선택한 값보다 큰 값들을 모두 오른쪽으로 한칸씩 이동시켰다.

 

이번에는 왼쪽값과 비교하여 선택값보다 큰 경우, swap해가며 이동하는 방법이다.

public static void insertionSort(int[] arr) {
    int n = arr.length;

    for(int i=1;i<n;i++){
        for (int j = i; j > 0; j--) {
            //i번인덱스부터 1까지 왼쪽과 비교해서 자기자신보다 크면 swap
            if(arr[j] < arr[j-1]){
                swap(arr, j, j-1);
            }else break;
        }
    }

}
private static void swap(int[] arr, int i, int j){
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

---

(참고)Do it! 알고리즘 코딩테스트 자바편
http://www.yes24.com/Product/Goods/108571508