[알고리즘] 삽입 정렬 (Insertion Sort) 개념 정리 및 코드 리뷰

감자 코딩에 감자 개발자입니다.  이번에 살펴볼 내용은 알고리즘의 Sort중 하나인 삽입 정렬(Insertion Sort)입니다.

1.삽입 정렬(Insertion Sort) 시간복잡도와 공간복잡도 

삽입정렬 (Insertion)의 시간복잡도는 O(N^2)

2. 삽입 정렬 원리

가장 먼저 삽입 정렬에서의 원리를 살펴봅시다.

가장 Array[0]에 있는 값과 Array[1],[2].....[N]까지의 값과 비교를 해갑니다.

이때, Array[0]와 비교해가면서 값의 크기를 비교합니다.값이 더 작으면Array[0]와 값을 바꿔치기해줍니다.

그리고, 바꿔치기한 값으로 부터 지금까지 진행비교 중이던 인덱스부터 다시 비교를 시작합니다. 

예를 들어 Array[0] 과 비교를해서 가다가 Array[2]에서 Array[2]값이 더작아서 값을 교환하였을 경우 Array[0] <-> Array[2] 값을 바꿔주고, 그 바꿔준 값 Array[2]가 Array[0]가 되면서 이제 Array[3]부터 다시 비교를 하기시작하여 Array[N]까지 이런방식으로 정렬을 해줍니다.

결론, 하나의 값을 기준으로 비교해가다가 작은값을 만나면 교체를 해주고 교체해준값을 또 기준으로 Array[N]까지 비교를 마친다라고 할 수 있습니다. 

이렇게 N까지 비교가 끝나면 Array[1]부터 다시 Array[N]까지 이와 동일한 방식으로 값을 비교해가면서 교체를 해주면 됩니다.

예)

크기가 5인 배열이 있다고 가정해봅시다.  4  7 8 2 10

1) 첫번째 순회

4 가 기준이되어 7 8 2 10 까지 값을 비교해 갑니다.  4보다 작은 값 2를 만나게 되면 (4 > 2)

4<->2를 교환해줍니다. 교환을 마치면 2 7 8 4 10 의 값이 됩니다.

이제 다시 2 7 8 4 10 에서 아직 비교를 안한 10을 비교 해줍니다. (10 > 2)

2보다 큰값이므로 값을 교환해주지 않습니다. 이제 첫번째 순회가 끝났습니다. 

2) 두번째 순회

배열 2 7 8 4 10 으로부터 다시 순회를 시작합니다. Array[0]는 비교를 하였으므로, 이제 Array[1]부터 시작합니다. 2를 기준으로 7 8 4 10 을 비교해나갑니다. 순회를 하다보면 7보다 작은 4를 만나게 됩니다.(7 > 4)

그러면 7과 4의 값을 교환하게 합니다. 7<->4 결국 2 4 8 7 10 의 값으로 배열이 정렬됩니다.

앞으로 남은 10과 다시 비교해봐도 (10 > 4) 4가 더 작습니다.

따라서 2번째 순회를 2 4 8 7 10 으로 종료하게됩니다.

3) 세번째 순회

2 4 8 7 10 에서 이제 Array[2]를 기준 8으로 7 10 을비교 하게 됩니다.( 8 > 7)

8과 비교하였을때 7이 더 작으니 값을 변경해줍니다.  2 4 7 8 10

값을 변경해주고 7을 기준으로 10과 비교하면 아직까지 7이 더 작은것을 알 수 있습니다.

세번째 순회에서 2 4 7 8 10 으로 정렬이 되었습니다.

4) 네번째 순회 

Array[3] 값인 8을 기준으로 10과 비교하게됩니다. (8 > 10) 이므로 10과의 값을 변화시키지 않습니다.

N까지 도달하였으므로 , 프로그램을 종료합니다.

결국 Array = {2,4,7,8,10} 으로 종료하게 됩니다.

5) Insertion Sort최종 결과

2 4 7 8 10 정상적으로 오름차순으로 정렬이 된것을 알 수 있습니다.

3. 삽입 정렬의 코드

public static void Insertion_Sort(int[] input){
    int i,j,key = 0;

    for(i=1; i<input.length; i++){
        key = input[i];

        for(j=i-1; j>=0; j--){

            if(key < input[j]){
                input[j+1] = input[j];
            }else{
                break;
            }
        }
        input[j+1] = key;
    }

}