삽입정렬 (insertion sort)

선택한 요소를 그보다 더 앞쪽의 이미 정렬된 배열 부분과 비교하여 알맞은 위치이 '삽입' 하는 작업을 반복하여 정렬

1. 두 번째 요소부터 선택하여 진행한다.
2. 앞의 요소와 비교하며 삽입할 위치를 찾는다.
   1. 두 번째 요소는 1 번째 요소와 비교
   2. 세 번째 요소라면 1, 2 번째 요소들과 비교
   3. 네 번째 요소라면 1, 2, 3 번째 요소들과 비교
3. 삽입할 위치를 찾았다면, 자료를 뒤로 옮겨 해당 위치에 자료를 삽입한다.
4. 정렬된 요소를 제외한 나머지 요소를 위와 동일하게 삽입한다. (반복)

삽입정렬 - 예시

• 정렬되지 않은 위의 항목들을 이용하여 선택정렬을 한다.
  

• 처음 왼쪽 끝은 이미 정렬이 됐다고 가정하여, 두 번째 요소부터 선택하여 정렬한다.
• 아직 작업되지 않은 항목중 가장 왼쪽의 숫자부터 정렬 대상이 된다.
• 앞의 정렬된 3과 비교했을 때, 3 > 1 이므로 3은 한칸 뒤로 이동하고, 1은 3이 있던 자리에 삽입된다.
  • 이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때 까지 반복한다.

• 1은 왼쪽 끝에 도달하였으므로 정렬이 완료됐다.
  

• 이번에는 작업되지 않은 항목 중 가장 왼쪽인 2가 정렬대상이다.
• 2를 기준으로 왼쪽의 정렬된 모든 항목들과 비교를 한다.
  • 바로 왼쪽 숫자인 3과 비교했을 때 3 > 2 이므로, 3은 한칸 뒤로 이동한다.
    

• 앞의 정렬된 1과 비교했을 때 1 < 2이므로, 자신보다 작은 숫자가 나왔기 때문에 이동을 멈추고
  해당 위치에 삽입된다.
  

• 세 번째 위치까지 정렬 완료
  

• 작업되지 않은 항목 중 가장 왼쪽에 있는 6을 선택한다.
• 6은 앞의 작업된 항목중 가장 오른쪽인 3보다 크다. 3 < 6
  • 따라서, 이동하지 않고 원래 있던 그 자리 그대로 정렬이 된다.
    

• 네 번째 위치까지 정렬 완료
• 앞의 작업들을 마지막 위치가 정렬될 때까지 반복하여 작업한다.
  

애니메이션

삽입정렬 전체 과정 애니메이션이다.

삽입정렬 - Java 코드

public class InsertionSortTest {

    static void insertSort(int[] arr) {

        // 첫 번째 값은 정렬이 됐다고 생각하고 두 번째 인덱스 부터 정렬 시작
       for (int i = 1; i < arr.length; i++) {

            // 삽입될 위치를 저장하기 위한 idx
            int idx = i;
            // 현재 정렬대상 값
            int tmp = arr[i];

            // 1. 이미 정렬된 배열에서 현재 정렬대상 값이 삽입될 위치(인덱스)를 찾는다.
            // 2. 현재 정렬대상 값보다 큰 값은 뒤로 한 칸식 이동된다.
            while( (idx > 0) && (arr[idx - 1] > tmp) ) {
                arr[idx] = arr[idx -1];
                idx--;
            }

            // 삽입될 위치에 tmp 삽입
            arr[idx] = tmp;
        }

    }

    public static void main(String[] args) {

        int[] arr = {3, 1, 2, 6, 7 , 5, 4};

        // 삽입정렬
        insertSort(arr);

        // 결과 출력
        System.out.println(Arrays.toString(arr));

    }
}

삽입정렬 특징

• 장점
  • 구현이 쉽다.
  • 선택정렬이나 버블정렬과 같은 O(n2) 알고리즘과 비교하여 빠르고, 안전한 정렬이다.
  • 대부분의 레코드가 이미 정렬되어있을 경우 매우 효율적일 수 있다.
    • 최선의 경우 이동없이 1번의 비교로 정렬되어 O(n) 시간복잡도를 갖는다.
• 단점
  • 많은 레코드들의 이동을 포함한다.
  • 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않다.
  • 평균~최악의 경우 시간복잡도 O(n2) 로 인하여 정렬 시간이 오래 걸림.

References

• 삽입정렬-위키백과
• https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html
• https://yabmoons.tistory.com/250
• 보요 시바타, 『자료구조와 함께 배우는 알고리즘 입문』, 이지스퍼블리싱(2018)
• 모든 이미지는 직접 그림