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

---

삽입 정렬(Insertion Sort) 이란?

이미 정렬되어 있는 i개 짜리의 배열에 하나의 원소를 더 더하여 정렬된 i+1 개의 배열을 만드는 과정을 A[n] 까지 반복하는 알고리즘 이다.

 

차이점이 있다면 지금까지 했던 선택 정렬 이나 버블 정렬은 n 개의 배열에서 시작하여 하나씩 원소를 줄이는데 반하여 삽입 정렬은 그 크기를 하나씩 늘리는 정렬이다.

 

하지만 선택 정렬이나 버블 정렬에 비하여 구현하기 조금 까다롭다는 점이 있다.

 

백문이 불여일타 라고 pseudo 코드를 한 번 가볍게 보고 직접 생각해보자.

insertionSort(A[], n){                    .... 1

    for i <- 2 to n                        .... 2

        A[1 ... i]의 적합한 자리에 A[i]를 삽입한다.    ....3

}

• 1번의 for 루프는 문제의 크기를 하나씩, 즉 정렬한 배열의 크기를 늘려 새롭게 원소를 추가하는 역할을 한다.( 원소를 추가하는 시점은 항상 정렬이 되어있다.)

• 2번을 수행하고 나면 A[1...i] 까지 정렬이 된다. 즉 이미 정렬된 원소 A[1...i-1]에 새롭게 A[i]를 추가시키고 여기서 조건이 있다.

• A[i] > A[i-1] 이면 A[i]는 A[1..i-1] 의 모든 원소보다 크므로 그냥 제자리에 두고 그렇지 않을 경우 왼쪽부터 차례대로 A[i]가 들어갈 자리를 찾아가면 된다.

insertionSort(A[], n){
    for i <- 2 to n {
        loc <- i-1;
        newItem <- A[i];

        while(loc>=1 and newItem<A[loc]){
            A[loc+1] <- A[loc];
            loc --;
        }
        A[loc+1] <- newItem;
    }
}

---

• 정렬되지 않은 배열 A[] = {7, 22, 31, 4, 11}이 있다고 치자. 각 정렬은 A[0] 부터 시작해 점차 인덱스를 하나씩 늘려가며 정렬을 할 것이다.

첫 번째 정렬

• 배열의 상태: {7}

배열인덱스를 추가한다. -> A[i] = A[i+1] -> 22 가 7보다 큰지 검사 -> 크므로 그 자리 유지 : {7, 22}

---

배열인덱스를 추가한다. -> A[i] = A[i+1] -> 31 이 22보다 큰지 검사 -> 크므로 그 자리 유지 : {7, 22, 31}

---

배열인덱스를 추가한다. -> A[i] = A[i+1] -> 4 가 31 보다 큰지 검사 -> 작으므로 원소 위치 검사

ㄴ> 배열 7이 4보다 큰지 검사 -> 크므로 7의 자리에 4 삽입 : {4, 7, 22, 31}

---

배열인덱스를 추가한다. -> A[i] = A[i+1] -> 11이 31 보다 큰지 검사 -> 작으므로 원소 위치 검사

ㄴ> 배열 4가 11보다 큰지 검사 -> 작으므로 배열 인덱스 한 칸 뜀 -> 7이 11보다 큰지 검사-> 작으므로 배열인덱스 한 칸 뜀 ->22가 11보다 큰지 검사 -> 크므로 22자리에 11 삽입 : {4, 7, 11, 22, 31}

---

삽입 정렬(Insertion Sort)의 시간 복잡도

위의 pseudo 코드에서 보면 반복은 총 두 번 등장한다
1 번의 for문 그리고 3번에 속해있는 while문. 입력의 크기가 n 일 때 반복은 n 에 관련이 있으므로 O(n^2)의 시간이 든다.

하지만 만약 배열이 완전히 정렬된 채로 입력된다면 while 루프는 한 번도 수행되지 않으므로 O(n)에 가까운 시간복잡도가 생성된다. 이런 매력 덥군에 다른 정렬을 사용하는 경우에도 상황에 따라 가끔 삽입정렬을 섞어서 쓰는 것도 권자된다.

---

삽입 정렬(Insertion Sort)의 특징

장점

• 안전한 정렬 방법이다.
• 배열의 수가 적을 수록 다른 정렬 방법보다 알고리즘 자체가 간단하므로 유리할 수 있다.
• 이미 배열이 정렬되었을 경우 극상의 효과를 볼 수 있다.

단점

• 시간복잡도의 관점에서 봤을 때 O(n^2)이므로 젼혀 효율적이지 않다.

---

삽입 정렬(Insertion Sort)의 자바 코드