[정렬] 삽입 정렬(Insertion Sort)

- 이미 정렬되어 있는 배열이 있다고 보고 한 원소를 그 배열에 삽입한다.

  (배열의 정렬 순서를 유지하도록 적절한 위치에 삽입)

- 이러한 작업을 반복한다.

 

 

다음은 삽입 정렬의 알고리즘이다.

insertionSort(A[], n){
    for i←2 to n{ // 1
        loc ← i-1;
        newItem ← A[i];
        // 이 지점에서 A[1...i-1]은 이미 정렬되어 있는 상태
        while (loc >= 1 and newItem < A[loc]) { // 2
            A[loc+1] ← A[loc];
            loc--;
        }
        A[loc+1] ← newItem;
    }
}

- 1의 for 루프는 n-1번 반복한다.

- 2의 최악의 경우는 i-1회 비교, 최선의 경우엔 1번 비교한다.

 

따라서,

최악의 경우 T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

시간 복잡도는 O(n^2)이 된다.