[Sort]Insertion Sort(삽입 정렬)

설명

• 주어진 키를 정렬된 리스트 중 자신의 위치에 삽입(Insertion)하면서 정렬하는 알고리즘
• 손 안에 카드를 정렬 하는 것과 유사하다.

예제

Pseudo Code

INSERTIONN-SORT(A)
    for j = 2 to A.length //첫번째 원소는 이미 정렬된 리스트라고 생각해 2번째 원소부터 정렬한다.  
            key = A[j] // 정렬을 수행할 원소

            i = j - 1
            // 오름차순 정렬
            while i > 0 and A[i] > key // j - 1 부터 1 번째 index로 가면서 삽입 될 위치를 찾는다.
                A[i+1] = A[i]
                i = i - 1

            A[i + 1] = key

시간 복잡도

1. Best Case

    7행에 있는 while 문이 실행되지 않는다 
    → \(O(N)\)

2. Worst Case

    7행에 있는 while 문이 j-1 부터 1 까지 모두 실행된다
    → \(O(N^2)\)

장점

• 단순한 구현
• Stable Sort(안정 정렬) 이다.
• In-Place Sort 이다.

단점

• 입력 데이터에 민감하다.
• 비효율적인 시간 복잡도

참고 자료

• Introduction to Algorithms, 3rd Ed
• tmxklab