[알고리즘] 삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort)

• 임의 값을 적절한 자리에 삽입하여 정렬하는 방식

코드 설계

• 배열의 가장 왼쪽부터 정렬한다는 기준을 잡기
• 변경 전 값을 기준 값과 비교하여 적절한 위치로 변경

코드 구현

    private int[] insertionSort(int[] A, int n) {
        int[] ret;

        for(int i = 1 ; i < n ; i++) {
            int value = A[i]; // 배열의 두 번째 값을 기준으로 시작
            int hole = i;

            while(hole > 0 && (A[hole-1] > value)) { // A[0] > A[1] 부터 비교하기를 시작
                // 과정 출력 not swap
                A[hole] = A[hole - 1];
                hole--;

            }
            A[hole] = value;
            // 과정 출력 swap
        }

        ret = A;
        return ret;
    }

• 과정

1:    2    7    4    1    5    3    : 1    

2:    2    7    4    1    5    3    : 2    
2:    2    4    7    1    5    3    : 1    

3:    2    4    7    1    5    3    : 3    
3:    2    4    7    7    5    3    : 2    
3:    2    4    4    7    5    3    : 1    
3:    1    2    4    7    5    3    : 0    

4:    1    2    4    7    5    3    : 4    
4:    1    2    4    5    7    3    : 3    

5:    1    2    4    5    7    3    : 5    
5:    1    2    4    5    7    7    : 4    
5:    1    2    4    5    5    7    : 3    
5:    1    2    3    4    5    7    : 2    

• 결과 확인

    int[] A = {2, 7, 4, 1, 5, 3};
    int[] except = {1, 2, 3, 4, 5, 7};
    int n = A.length;

    @Test
    public void testInsert() {
        assertThat(insertionSort(A, n), is(except));
    }

분석

• 복잡도 분석
  • Bast-Case O(n)
  • Average-Case O(n^2)
  • Worst-Case O(n^2)
• 삽입 정렬은 선택정렬, 버블정렬보다 효율적인 알고리즘이다.
• 직관적인 알고리즘