삽입정렬

---

삽입 정렬(Insertion Sort)

0. 개요

• ⭐두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘
• 오름차순을 기준으로 정렬.
• 만약, 내림차순을 기준으로 정렬하고 싶다면 부등호 반대방향

1. 삽입 정렬(Insertion Sort)이란?

• 손 안의 카드를 정렬하는 방법과 유사
  - 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리에 삽입
  - 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드 정렬됨
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

2. 삽입 정렬(insertion sort)알고리즘의 구체적 개념

• ⭐삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘.
• 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. ⭐자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

3. 삽입 정렬(insertion sort) 알고리즘 예제

• 배열에 8, 5, 6, 2, 4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해보기.
  

4. 삽입 정렬(insertion sort) 코드

1. C언어

# include <stdio.h>
# define MAX_SIZE 5

// 삽입 정렬
void insertion_sort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j 값은 음수가 아니어야 되고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    for(j=i-1; j>=0 && list[j]>key; j--){
      list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
    }

    list[j+1] = key;
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {8, 5, 6, 2, 4};

  // 삽입 정렬 수행
  insertion_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}
//https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

2. Python 코드

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

3. Java 코드

public class Insertion {
    public static void sort(int[] arr) {
        for (int end = 1; end < arr.length; end++) {
            for (int i = end; i > 0; i--) {
                if (arr[i - 1] > arr[i])
                    swap(arr, i - 1, i);
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

4. Java 직접 구현해보기

static void insertionSort(int[] arr) {
        int key = 0;    //⭐ 매 턴마다 비교의 기준이 될 값을 key로
        int j = 0;
        for(int i=1; i<arr.length; i++) {
            key = arr[i];
            j = i-1;    //⭐ j=i--로 두면 i의 값이 먼저 1감소된 후 j에 반영되기 때문에 j=i-1과 의미상으로 전혀 다르다.
            while(j>=0 && arr[j]>key) { //⭐ j가 0이상이어야, 인덱스 참조 가능. arr[j]가 key값보다 높을 때 순서를 바꿔주는 조건문
                arr[j+1] = arr[j];      //⭐arr[j+1]을 arr[i]로 놓을시 i의 위치는 고정된 상태이므로, 뜬금없이 이미 순서를 바꾼 자리에 arr[j]가 들어간다.
                arr[j] = key;
                j--;
            }
        }
    }

• ⭐ j=i-1과 j=i--은 전혀 다른 내용이다. 후자는 증감연산자가 먼저 적용된 다음 j의 값에 저장되므로, 결국 i의 값이 변할 뿐더라 j의 값도 동일한 값으로 바뀐다.
• 💡 arr[j+1]=arr[j] 비교의 기준자를 반드시 생각해야 한다. 비교 기준자 인덱스가 한 칸씩 줄어든다면 비교 대상도 한 칸씩 줄어 들어야 한다. arr[j+1]=arr[i]는 얼핏 비슷해보이지만, i가 루프문 바깥에서 고정된다는 점에서 전혀 다르다. (처음 시작할 때만 i가 j보다 1 큰 값인 것)

5. 삽입 정렬(insertion sort) 알고리즘 특징

1. 장점

• 안전한 정렬 방법
• 레코드 수가 먹을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
• 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적

2. 단점

• 비교적 많은 레코드들의 이동을 포함한다.
• 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

3. 그 외

• 배열 내에서 교환하는 방식이므로 공간복잡도는 O(1)이다. 기껏해야 원소를 교환할 때 쓰일 임시변수 정도의 추가공간만 필요하므로 in-place 정렬이다.
• 평균과 최악의 시간복잡도는 O(n^2)이다.
• 삽입 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.
• 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다.

6. 삽입 정렬의 시간복잡도

1. 최선의 경우

• 비교 횟수
  - 이동 없이 1번의 비교만 이루어진다.
  - 외부 루프: (n-1)번
• Best T(n) = O(n)

2. 최악의 경우(입력 자료가 역순일 경우)

• 비교 횟수
  - 외부 루프 안의 각 반복마다 i번의 비교 수행
  - 외부 루프: (n-1)+(n-2)+...+2+1 = n(n-1)/2 = O(n^2)
• 교환 횟수
  - 외부 루프의 각 단계마다 (i+2)번의 이동 발생
  - n(n-1)/2+2(n-1)=(n^2+3n-4)/2 = O(n^2)
• WorstT(n) = O(n^2)

7. 최적화

• ⭐기존에 있던 값들은 이전 패스에서 모두 정렬되었다는 점을 활용하면 불필요한 비교 작업을 제거할 수 있습니다. 예를 들면, 아래와 같이 기존 정렬 범위 [1, 2, 3, 5]에 4가 새롭게 추가된다면, 5는 4보다 크기 때문에 swap이 필요하지만, 3은 4보다 작기 때문에 swap이 필요없습니다. 그리고 3보다 앞에 있는 숫자들은 기존 패스에서 이미 정렬을 해놓았기 때문에 당연히 3보다는 작을 것이며, 더 이상의 4와 대소 비교는 무의미합니다. 이 사실을 이용하면, 새롭게 추가된 값보다 작은 숫자를 만나는 최초의 순간까지만 내부 반복문을 수행해도 됩니다.

[1, 2, 3, 5, 4, ...]: 5 > 4 => swap
 *  *  *  *  ^
[1, 2, 3, 4, 5, ...]: 3 < 4 => OK => all sorted!
 *  *  *  *  *

1. Python 코드

def insertion_sort(arr):
    for end in range(1, len(arr)):
        i = end
        while i > 0 and arr[i - 1] > arr[i]:
            arr[i - 1], arr[i] = arr[i], arr[i - 1]
            i -= 1

2. Java 코드

public class Insertion {
    public static void sort(int[] arr) {
        for (int end = 1; end < arr.length; end++) {
            int i = end;
            while (i > 0 && arr[i - 1] > arr[i]) {
                swap(arr, i - 1, i);
                i--;
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

• ⭐이 최적화를 적용하면, 정렬된 배열이 들어올 경우, O(N)의 시간 복잡도를 달성할 수 있습니다. 예를 들어, 다음과 같이 5개의 숫자가 된 배열이 들어오면 각 패스 당 단 한 번 총 4번의 비교만으로 해당 배열이 완전히 정렬되었음을 알아내고 삽입 정렬을 완료할 수 있습니다.

    [1, 2]: 1 < 2 => all sorted!
    [1, 2, 3]: 2 < 3 => all sorted!
    [1, 2, 3, 4]: 3 < 4 => all sorted!
    [1, 2, 3, 4, 5]: 4 < 5 => all sorted!

8. 추가 최적화

• ⭐swap 작업없이 단순히 값들을 shift 시키는 것만으로도 삽입 정렬의 구현이 가능합니다. 앞의 값이 정렬 범위에 추가시킨 값보다 클 경우 앞의 값을 뒤로 밀다가 최초로 작은 값을 만나는 순간 그 뒤에 추가된 값을 꼽으면 됩니다.

def insertion_sort(arr):
    for end in range(1, len(arr)):
        to_insert = arr[end]
        i = end
        while i > 0 and arr[i - 1] > to_insert:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = to_insert

public class Insertion {
    public static void sort(int[] arr) {
        for (int end = 1; end < arr.length; end++) {
            int toInsert = arr[end];
            int i = end;
            while (i > 0 && arr[i - 1] > toInsert) {
                arr[i] = arr[i - 1];
                i--;
            }
            arr[i] = toInsert;
        }
    }
}

9. 정렬 알고리즘 시간복잡도 비교

• 단순(구현 간단)하지만 비효율적인 방법
  : 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법
  : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

출처

1. [알고리즘] 삽입 정렬(insertion sort)이란
2. 삽입 정렬(Insertion Sort)
3. [알고리즘] 삽입 정렬 - Insertion Sort (Python, Java)
4. 인설션소트 삽입정렬 5분만에 이해하기 - Gunny