삽입 정렬 (Insertion Sort)

정렬 알고리즘

 

 

 

삽입 정렬 (Insertion Sort)

기초적인 정렬 방법 중 하나 입니다. 

인덱스의 값이 왼쪽보다 작다면 위치를 교환합니다. 이 과정을 왼쪽보다 클 때까지 반복합니다. 

이 과정을 반복하면 왼쪽에 정렬된 부분이 생깁니다. 정렬된 부분에 새로운 값이 삽입되므로 삽입 정렬이라 합니다.

삽입된 값은 왼쪽이 자기보다 작을 때까지 교환합니다. 이 과정을 통해 자기 자리를 찾아 정렬을 완성합니다. 

 

시간 복잡도는 O(N^2) 입니다. 버블 정렬, 선택 정렬 보다 평균적인 정렬 속도가 빠릅니다.

평균적인 정렬 속도 : 버블 < 선택 < 삽입 

 

삽입 정렬은 작은 데이터셋에서 효율적입니다. 또한, 동일한 요소가 있을 경우 정렬한 후에 순서가 지켜져 안정적입니다.

삽입 정렬은 이후에 팀소트(TimSort)에서 작은 크기로 나눠진 부분인 런(Run)들을 정렬하는데 사용됩니다. 

 

 

동작 과정

시간 복잡도 : O(n^2)

 

1. 시작 : 정렬되지 않은 배열에서 첫 번째 요소를 이미 정렬된 부분으로 간주합니다. 

2. 요소 선택 : 정렬되지 않은 부분에서 요소를 선택합니다.

3. 위치 탐색 및 삽입 : 선택한 요소를 이미 정렬된 부분의 적절한 위치에 삽입합니다. 이를 위해, 선택된 요소보다 큰 모든 요소는 오른쪽으로 한 칸씩 이동합니다. 왼쪽 요소의 값이 선택한 요소보다 작을 때까지 스왑을 합니다. 

4. 반복 : 배열의 모든 요소가 정렬될 때까지 2번, 3번 과정을 반복합니다.

 

 

예시

초기 배열 

int[] array = {3,1,4,2,6,5} 

3

1

4

2

6

5

 

 

 

첫 번째 요소인 array[0] = 3 은 정렬된 요소로 간주 합니다. 

정렬된 부분은 0 입니다. 

3

1

4

2

6

5

 

 

 

다음 선택한 요소는 array[1] = 1 입니다. 

왼쪽 값인 3이 더 크므로 자리를 바꿉니다. 

첫 번째 위치에 왔으므로 더 이상 바꿀게 없으니 교환을 멈춥니다.

정렬된 부분은 0 ~ 1 입니다. 

1

3

4

2

6

5

 

 

다음 선택한 요소는 array[2] = 4 입니다. 

왼쪽 값보다 크므로 자리를 바꾸지 않습니다.

정렬된 부분은 0 ~ 2 입니다. 

1

3

4

2

6

5

 

 

다음 선택한 요소는 array[3] = 2 입니다. 

왼쪽에는 2보다 큰 값인 4가 있습니다. 위치를 교환합니다. 

1

3

2

4

6

5

 

 

다음 왼쪽에는 2보다 큰 값인 3이 있습니다. 위치를 교환합니다.

다음 왼쪽에는 1이므로 자신보다 작아 정렬된 자리를 찾았습니다. 

정렬된 부분은 0 ~ 3 입니다. 

1

2

3

4

6

5

 

 

다음 선택한 요소는 array[4] = 6 입니다. 

왼쪽 보다 크므로 교환하지 않습니다.

정렬된 부분은 0 ~ 4 입니다. 

1

2

3

4

6

5

 

 

다음 선택한 요소는 array[5] = 5 입니다.

왼쪽은 6이므로 자신보다 크므로 교환합니다. 

다음 왼쪽은 4 이므로 자신보다 작아 교환을 멈춥니다. 

정렬된 부분은 0 ~ 5로 모든 부분을 정렬했습니다. 

1

2

3

4

5

6

 

 

 

Java 코드 구현

삽입 정렬을 자바 코드로 구현하면 다음과 같습니다.

/*
삽입 정렬
시간 복잡도 : O(n^2)

선택한 요소를 이미 정렬된 배열 부분의 적절한 위치에 삽입
배열을 순회하면서 뒤에게 작으면 계속 앞으로 보낸다. 앞이 더 작으면 멈춘다.
즉, 정렬된 부분에 다음 값이 적절한 위치에 오도록 삽입하므로 삽입 정렬 이다.
 */
public class InsertionSort {

  public static void main(String[] args) {
    int[] array = {3,1,5,9,4,8,7};
    printArray(array);
    insertionSort(array);
    printArray(array);
  }

  public static void insertionSort(int[] array) {
    int n = array.length;

    for(int i = 1; i < n; i++) {
      int key = array[i];
      int j = i - 1;

      // key 보다 큰 array[j]를 한 위치 뒤로 이동 (작은 값을 앞으로 이동)
      while(j >= 0 && array[j] > key) {
        array[j+1] = array[j];
        j = j - 1;
      }
      array[j+1] = key;
    }
  }

  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

마무리 

기초적인 정렬인 버블, 선택, 삽입 정렬에 대해서 정리했습니다.

삽입 정렬은 3개 중 평균적인 속도가 빠르며 팀소트에서도 사용하니 알아두면 좋을 거 같습니다.

다음에는 비교를 사용하지 않는 정렬인 계수 정렬(Counting Sort), 기수 정렬(Radix Sort)에 대해 정리해 보겠습니다.

감사합니다. 

 

 

 

참고 사이트

버블 정렬, 선택 정렬, 삽입 정렬 

https://www.youtube.com/watch?v=Bor_CRWEIXo&t=2s