CSAlgorithm

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

Algorithm, CS

삽입정렬

1. 삽입정렬의 개념

삽입정렬은 index 1 부터 순서대로 index 위치의 값을 앞 부분의 적당한 위치에 삽입하며 정렬하는 것이다.
그럼 7, 9, 5, 1, 3 을 오름차순으로 삽입정렬해보자.

1 단계 - index 1)

  1. 먼저 index 1 의 값인 9를 따로 특정 변수에 저장해 둔 다음에, 이 기준값인 9를 기준으로 왼쪽의 값들과 비교를 한다. 비교를 했을 때 기준값보다 왼쪽에 위치한 값이 더 크다면 오른쪽으로 한 칸 복사 이동 한다. 7, 9, 5, 1, 3에서 7은 9보다 크지 않기 때문에 이동시키지 않는다.

7 9 5 1 3

2 단계 - index 2)

  1. 7, 9, 5, 1, 3에서 index 2 의 값인 5를 따로 특정 변수에 저장해 둔 다음에, 이 기준값인 5를 기준으로 왼쪽의 값들과 비교를 한다. 먼저 index 2 의 바로 왼쪽인 index 1 의 값과 비교를 한다. index 1 의 값인 9는 기준값인 5보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 7, 9, 9, 1, 3이 된다.
  2. 그 다음, 한 칸 더 왼쪽인 index 0 의 값과 비교를 한다. index 0 의 값인 7은 기준값인 5보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 7, 7, 9, 1, 3이 된다.
  3. 더 이상 왼쪽에 비교할 값이 없기 때문에 처음에 특정 변수에 저장해 둔 기준값 5를 index 0 에 넣는다. 그럼 5, 7, 9, 1, 3으로 정렬이 된다.

7 9 5 1 3
7 9 9 1 3
7 7 9 1 3
5 7 9 1 3

3 단계 - index 3)

  1. 5, 7, 9, 1, 3에서 index 3 의 값인 1을 따로 특정 변수에 저장해 둔 다음에, 이 기준값인 1을 기준으로 왼쪽의 값들과 비교를 한다. 먼저 index 3 의 바로 왼쪽인 index 2 의 값과 비교를 한다. index 2 의 값인 9는 기준값인 1보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 5, 7, 9, 9, 3이 된다.
  2. 그 다음, 한 칸 더 왼쪽인 index 1 의 값과 비교를 한다. index 1 의 값인 7은 기준값인 1보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 5, 7, 7, 9, 3이 된다.
  3. 그 다음, 한 칸 더 왼쪽인 index 0 의 값과 비교를 한다. index 0 의 값인 5는 기준값인 1보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 5, 5, 7, 9, 3이 된다.
  4. 더 이상 왼쪽에 비교할 값이 없기 때문에 처음에 특정 변수에 저장해 둔 기준값 1을 index 0 에 넣는다. 그럼 1, 5, 7, 9, 3으로 정렬이 된다.

5 7 9 1 3
5 7 9 9 3
5 7 7 9 3
5 5 7 9 3
1 5 7 9 3

4 단계 - index 4)

  1. 1, 5, 7, 9, 3에서 index 4 의 값인 3을 따로 특정 변수에 저장해 둔 다음에, 이 기준값인 3을 기준으로 왼쪽의 값들과 비교를 한다. 먼저 index 4 의 바로 왼쪽인 index 3 의 값과 비교를 한다. index 3 의 값인 9는 기준값인 3보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 1, 5, 7, 9, 9가 된다.
  2. 그 다음, 한 칸 더 왼쪽인 index 2 의 값과 비교를 한다. index 2 의 값인 7은 기준값인 3보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 1, 5, 7, 7, 9가 된다.
  3. 그 다음, 한 칸 더 왼쪽인 index 1 의 값과 비교를 한다. index 1 의 값인 5는 기준값인 3보다 크기 때문에 오른쪽으로 한 칸 복사 이동 한다. 복사 이동을 하게 되면 1, 5, 5, 7, 9가 된다.
  4. 그 다음, 한 칸 더 왼쪽인 index 0 의 값과 비교를 한다. index 0 의 값인 1은 기준값인 3보다 작기 때문에 이동 시키지 않고 처음에 특정 변수에 저장해 둔 기준값 3을 index 1 에 넣는다. 그럼 1, 3, 5, 7, 9로 정렬이 된다.

1 5 7 9 3
1 5 7 9 9
1 5 7 7 9
1 5 5 7 9
1 3 5 7 9

완료

1 3 5 7 9


2. 삽입정렬 시간복잡도

최선 평균 최악
O(n) O(n^2) O(n^2)


3. 삽입정렬 JAVA 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 삽입정렬
static void insertionSort(int[] a) {
    for(int i=1; i<a.length; i++) {
        int value = a[i]; // 삽입할 값 보관
        int j;
        for(j=i-1; j>=0; j--) { // 뒤로 이동
            if(a[j] > value) a[j+1] = a[j];
            else break;
        }
        a[j+1] = value; // 값 삽입
    }
}

public static void main(String[] args) {
    int[] a = {7, 9, 5, 1, 3};
    insertionSort(a);
    System.out.println(Arrays.toString(a)); // 출력결과 : [1, 3, 5, 7, 9]
}
Share