삽입정렬(Insertion sort) 알고리즘

삽입정렬(Insertion sort)

삽입 정렬은 정렬이 우리가 카드놀이 할때 카드를 받아 정렬하는 것 처럼 즉 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬 하는 방법 입니다. 예를 들어 5장의 카드 A, 4, 7, J, 2를 순서대로 받았을 때 A, 4, 7, J는 정렬된 부분이므로 손대지 않고 2를 A와 4 사이에 집어 넣는 것을 떠올리시면 됩니다. 

배열  arr[5]={1, 4, 7, 10, 2} 을 가지고 삽입 정렬을 설명 해보겠습니다. 

{ 1, 4, 7, 10, 2 } temp = 4

배열의 첫번째는 이미 정렬 되어 있다고 가정하고 2번째 값 (arr[1]) 부터 시작합니다. 

먼저 배열의 2번째 값을 임시 변수(temp)에 저장하고 배열의 첫번째 값과 비교 합니다. 

arr[0]<temp 이므로 두 수는 올바르게 정렬되어 있습니다. 따라서 임시 변수에 저장된 값은 다시 원래 위치에 넣어줍니다. 

{ 1, 4, 7, 10, 2 } temp = 7

다음으로 arr[2]을 선택해 임시 배열의 저장하고 이전 배열의 값들과 비교 합니다. 

arr[1]<temp 그리고 arr[0]<temp 이므로 다시 원래 위치로 넣어줍니다. 

마찬가지 방법으로 배열은 arr[3] 까지 정렬 되어 있으므로 생략하겠습니다.  

...

{ 1, 4, 7, 10, 2 } temp = 2

다음으로 arr[4]을 선택해 임시 배열의 저장하고 이전 배열의 값들과 비교 합니다.

arr[3]>temp 이므로 arr[3]을 arr[4]로 밀어냅니다.  { 1, 4, 7, 10, 10 } temp=2 

arr[2]>temp 이므로 arr[2]를 arr[3]으로 밀어냅니다. { 1, 4, 7, 7, 10 } temp=2

arr[1]>temp 이므로 arr[1]을 arr[2]로 밀어냅니다. { 1, 4, 4, 7, 10 } temp=2 (빨간숫자는 의미없는 값.)

arr[0]<temp 이므로 temp의 저장된 값을 비어 있는 칸(의미없는 값) 에 넣어주면 정렬이 완료 됩니다.  { 1, 2, 4, 7, 10 }

삽입 정렬은 데이터가 역순으로 주어졌을때 최악의  의 실행 시간을 가집니다.  

간단하게 구현할 수 있으므로 자료수가 적거나 배열이 거의 정렬 되 어있을때 유용 할 수 있습니다.

다음은 자바로 구현한 삽입정렬 입니다.

    //정렬된 부분에 정렬되지 않은 데이터를 삽입하는 방법.
    //간단하게 구현 할 수 있음.
    //최악의 경우 시간복잡도 O(n^2)
    //자료수가 적거나 자료의 정렬 정도가 높을때 적용.
 
    public void sort(int[] arr) {
 
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i]; // 임시 변수에 대상 배열 값을 저장한다.
            int j;
            for (j = i - 1; j >= 0; j--) {
                if(arr[j]<temp){ //임시변수가 비교하는 대상보다  클때 탐색 종료.
                    break;
                }else{
                    arr[j+1]=arr[j]; //임시변수가 비교 대상보다 작다면 대상을 한칸 밀어낸다.
                }
            }
            arr[j+1]=temp; //임시변수에 저장한 값을 비어있는 위치에  삽입한다.
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 4, 7, 10, 2};
        new InsertSort().sort(arr);
        
        for (int a : arr) {
            System.out.print(a + " ");
        }
        
        //출력 : 1 2 4 7 10
 
    }

덧) 삽입 정렬의 비교의 횟수를 줄이기 위해 이진 검색(Binary Search) 을 이용 할 수 있습니다. 

//삽입정렬에서 탐색에 걸리는 시간은  최악의 경우 i번째반복시 O(i) 
//이진탐색을 통해 탐색시간을  O(Logi)로 줄일 수 있다. 
//그러나 전체 알고리즘은 삽입에 필요한 시간 때문에 O(n^2)을 가짐. 
    
    public int serach(int[] arr, int left, int right, int x) {
        
        if (right >= left) {
            int mid = left + ((right-left)/ 2);
            
            //찾는 값(x)과 배열의 요소가 일치하면 배열의 인덱스를 반환한다.
            if (arr[mid] == x)
                return mid;
            //찾는 값(x)보다 배열의 요소가 크다면 배열의 오른쪽 절반을 무시한다.
            if (arr[mid] > x)
                return serach(arr, left, mid-1, x);
            //찾는 값(x)보다 배열의 요소가 작다면 배열의 왼쪽 절반을 무시한다.
            return serach(arr, mid+1, right, x);
        }
        //일치하는 값이 없다면 배열의 맨 왼쪽 인덱스 반환
        return left;
    }
 
    
    public void sort(int[] arr) {
        
        int temp,find_Index,j;     //임시변수, 탐색결과가 들어갈 변수 선언
 
        for (int i = 1; i < arr.length; i++) {
            temp = arr[i]; // 임시 변수에 대상 배열 값을 저장한다.
            find_Index= serach(arr, 0, i, temp); 
            //임시변수 값이 들어갈 인덱스를 이진탐색한다. serach() 메소드 참조
                                    
            for (j = i - 1; j >= find_Index; j--) {
                    arr[j+1]=arr[j]; 
            } //선택된 배열부터 임시변수 값이 들어갈 자리까지 오른쪽으로 한칸씩 밀어낸다.
            
            arr[find_Index]=temp; //임시변수에 저장한 값을 이진탐색을 통해 찾은 인덱스에  삽입한다.
        }
    }