[Java]정렬 : 삽입 정렬(Insertion Sort)

 지난 시간까지 학습했던 선택 정렬과 버블 정렬을 다시 한 번 떠올려 봅시다.

선택 정렬의 메커니즘은 "가장 작은 것을 맨 앞으로 보내면 어떨까?"

버블 정렬의 메커니즘은 "옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까?"

두 정렬 알고리즘 모두 O(N*N)의 시간복잡도를 가졌고, 실제 속도는 버블정렬이 더 느린 것을 배웠습니다.

 

그렇다면, 삽입 정렬(Insertion Sort)는 어떨까요?

 

결론부터 말하자면, 두 정렬 알고리즘과 똑같이 O(N*N)의 시간 복잡도를 가집니다. 하지만, 특정한 상황에서는 정렬 알고리즘 중에서도 가장 빠른 정렬 알고리즘이라고 할 수도 있습니다.

 

서론이 길었네요.

---

1 10 5 8 7 6 4 3 2 9 를 오름 차순으로 정렬하는 프로그램을 작성하시오.

삽입 정렬(Insertion Sort)는 쉽게 말해서,
각 숫자를 적절한 위치에 삽입하는 것(이때, 선택한 요소의 앞에 있는 요소들은 정렬 되어있다고 가정)

---

 

앞으로 배울 다양한 알고리즘에 비하면, O(N*N)이라는 시간복잡도를 가진 이 삽입 정렬 알고리즘은 exponential 시간 복잡도이므로, 굉장히 느린 알고리즘이라고 할 수 있습니다. 하지만!! 특정한 상황에서는 굉장히 효율적인 알고리즘입니다. 코드부터 봅시다.

package sort;

public class Insertion_sort {
    public static void main(String[] args) {
        int temp;
        int[] array = {1,10,5,8,7,6,4,3,2,9};
        for (int i = 0; i < 9; ++i) {
            j=i;
            while(array[j]>array[j+1]){
                temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                --j;
            }
        }

        for(int i=0;i<10;++i){
            System.out.print(array[i]+" ");
        }
    }
}

---

앞서 언급했듯이 삽입 정렬은 정렬이 되어있다고 가정한다고 하였는데, 정확히 어떠한 메커니즘인지 그림을 통해 확인해봅시다.

 

삽입정렬

위 그림에서 빨간색 박스의 왼쪽부분은 오름차순으로 정렬이 되어있다고 가정하는 것입니다.

 

다시 우리 예제로 돌아와서 봅시다.
1 10 5 8 7 6 4 3 2 9 을 오름차순으로 정렬하시오.

 

i=0) 10을 정렬하여 삽입하기 위해 _ 1 _ 10 5 8 7 6 4 3 2 9 어디에 삽입할까요?                                                                ↑

                                              이 부분에 삽입해야 앞 쪽이 정렬이 유지된 채로 삽입이 되겠죠. 따라서, 10은 제자리 그대                                                로 있습니다.  [Result] 1 10 5 8 7 6 4 3 2 9

 

i=1)  5를 앞쪽 어딘가에 정렬되도록 삽입해봅시다. 1 _ 10 _ 5 8 7 6 4 3 2 9 어디에 삽입할까요?

                                                                                        ↑  

                                                 이 부분에 삽입해야 앞 쪽이 정렬이 유지된 채로 삽입이 되겠죠. 따라서, 5는 1과 10 사이                                                   로 이동합니다. [Result] 1 5 10 8 7 6 4 3 2 9

 

i=2) array[2+1]에 있는 8을 앞쪽 어딘가에 정렬되도록 해보죠. 1 5 _ 10 _ 8 7 6 4 3 2 9

                                                                                                               ↑

                                             이 부분에 삽입해야 앞 쪽이 정렬이 유지된 채로 삽입이 되겠죠. 따라서, 8는 5과 10 사이                                                   로 이동합니다. [Result] 1 5 10 8 7 6 4 3 2 9    

 

계속 위와 같이 정렬해 나가다 보면 1 2 3 4 5 6 7 8 9 10 으로 정렬이 될 것입니다.

 

---

삽입 정렬의 시간 복잡도 = O(N*N)

또, O(N*N)이라고요?(네, 최악의 경우인 입력 자료가 역순일 때요.)

 

하지만, 같은 시간복잡도임에도 삽입 정렬(insetion sort)라는 네이밍이 되어 알고리즘으로 존재하는 이유가 있겠죠?

 

바로, 아까 미리 언급을 두었던 "특수한 상황에서 강력한 정렬 알고리즘" 이기 때문입니다.

그 특수한 상황은 "거의 정렬된 상태"에서 아주 강력하기 때문이죠.

 

극단적인 예를 들어봅시다.

2 3 4 5 6 7 8 9 10 1 을 오름차순으로 정렬하는 프로그램을 작성하시오

라는 문제가 주어졌다고 하죠. 0번째부터 8번째 까지는 이미 오름 차순 정렬된 상태이네요.

2 3 4 5 6 7 8 9 10 까지 모두 swap하는 작업 없이 진행되고 

 2 3 4 5 6 7 8 9 1 10

 2 3 4 5 6 7 8 1 9 10

 2 3 4 5 6 7 1 8 9 10

 ...

 1 2 3 4 5 6 7 8 9 10 

이런 식으로 1만 앞자리와 비교하면 되겠군요.

 

다른 상황도 생각해보면 아시겠지만, 선택 정렬과 버블 정렬은 정렬이 끝났음을 인지하지 못하고 계속해서 반복을 이어 나가는데 비해 삽입 정렬은 이미 앞 쪽이 '정렬이 되어 있다고 가정'한다는 점에서 정렬이 거의 된 상태의 집합의 요소를 정렬할 때에는 굉장히 빠른 속도를 자랑합니다.

---

[삽입 정렬을 완전히 이해하기 위해서 삽입 정렬 수행 과정을 출력하는 프로그램을 작성해 봅시다.]

<예시 입력>

10

26 5 37 1 61 11 59 15 48 19

 

<예시 출력>

26

5 26

5 26 37

1 5 26 37

1 5 26 37 61

1 5 11 26 37 61

1 5 11 26 37 59 61

1 5 11 15 26 37 59 61

1 5 11 15 26 37 48 59 61

1 5 11 15 19 26 37 48 59 61

 

package sort;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Insertion_sort {
    public static void main(String[] args) {
//        int temp;
//        int[] array = {1,10,5,8,7,6,4,3,2,9};
//        for (int i = 0; i < 9; ++i) {
//            while(array[i]>array[i+1]){
//                temp=array[i];
//                array[i]=array[i+1];
//                array[i+1]=temp;
//                --i;
//            }
//        }
//
//        for(int i=0;i<10;++i){
//            System.out.print(array[i]+" ");
//        }

        /*보충 학습 정렬 과정 출력하는 프로그램*/
        Scanner sc = new Scanner(System.in);
        int i,j,temp;
        int n = sc.nextInt();
        int[] array = new int[101];

        for (i = 0; i < n; ++i) {
            array[i] = sc.nextInt();
        }

        for (i = 0; i < n-1; ++i) {
            j=i;
            while (j>0 && array[j-1]>array[j]){
                temp = array[j-1];
                array[j-1] = array[j];
                array[j]=temp;
                --j;
            }

            for (j = 0; j < i + 1; ++j) {
                System.out.print(array[j] + " ");
            }
            System.out.println();
        }

    }
}

처음에는 while내부 반복을 위한 증감 변수로 j가 아닌 i를 그대로 진행하였다. 안일했다.

while문 내부에는 감소연산자가 있기 때문에 i변수를 그대로 사용하면, for문에서 i가 점점 증가해도 다시 while문 내부에서 감소 시키므로 원하는 결과를 얻지 못하게 된다. (따라서, 주석처리된 부분이 처음 삽입 정렬을 설명했을 때, 사용했던 코드인데 다시 수정해두었다.)

---

정리해보자,
지금까지 배운것은
-선택 정렬 O(N*N)
-버블 정렬 O(N*N)
-삽입 정렬 O(N*N)
모두 같은 시간 복잡도 이지만,
버블 정렬은 인접한 값을 무조건적으로 swap하기에 가장 비효율적인 정렬 알고리즘
선택 정렬은 기억하고 마지막에 바꾸므로 버블보단 좋은 정렬 알고리즘
삽입 정렬은 거의 정렬된 상태일 수록 좋은 정렬 알고리즘

선택 정렬 메커니즘: "작은 것을 기억해두었다 맨 앞으로"
버블 정렬 메커니즘: "옆에 있는것과 비교해서 작은 것을 앞으로"
삽입 정렬 메커니즘: "각 숫자를 적절한 위치에 삽입(앞 쪽은 이미 정렬되었다고 가정이 핵심)"

다음에 퀵 정렬(Quick Sort)의 시간 복잡도와 작동 원리를 학습해보도록 하겠습니다.