[알고리즘] insertion sort 복습

인지 코드

INSERTION-SORT(A)  /* A is an array of numbers */
1	for j <- 2 to length[A]
2		do key <- A[j]
3			/* insert A[j] into the sorted sequence A[1 .. j-1] */
4			i <- j - 1
5			while i > 0 and A[i] > key
6				do A[i+1] <- A[i]
7					i <- i - 1
8			A[i+1] <- key

설명

간단하게 정리하면
배열 두 번째 원소부터 하나씩 뽑아온다 (key)
뽑은 원소보다 큰 애들은 오른쪽으로 한 칸씩 밀어낸다.
비어진 자리에 key를 꽂는다.
이걸 끝까지 반복하면 정렬 완료

j를 2부터 시작하는이유는 배열의 첫번째 인덱스를 i=1로 두기 위함이다
이유는 배열의 첫번째 인덱스가 0이면 나중에 다른 알고리즘쓸때 인덱스 0에 무언갈 곱하거나 할때
0에는 어떤것을 곱해도 0이기때문이여서 습관들이기 위함

example 5,2,4,6,1,3

c코드

void insertion_sort(int A[], int n) {
    int j, i, key;

    // for j <- 2 to n
    for (j = 2; j <= n; j++) {
        key = A[j];       // key <- A[j]
        i = j - 1;        // i <- j - 1

        // while i > 0 and A[i] > key
        while (i > 0 && A[i] > key) {
            A[i + 1] = A[i];   // A[i+1] <- A[i]
            i = i - 1;         // i <- i - 1
        }
        A[i + 1] = key;        // A[i+1] <- key
    }
}

시간복잡도

best case(이미 정렬된 경우):

이미 오름차순 정렬된 배열이라면 A[i] > key 조건은 항상 거짓.

따라서 while문은 한 번도 실행되지 않음.

각 단계에서 비교 1번만 수행 → 전체 비교 횟수는 n-1번.

​

0 <= n−1 ∈ O(n)

Best Case의 시간 복잡도는 O(n) 이다.

worst case(반대로 정렬이 되어있는 경우):

가장 안 좋은 경우: 매번 key가 맨 앞까지 밀려야 함.

즉, j번째 원소를 삽입할 때 j-1번 비교 & 이동.

총 실행 횟수 T(n):

(n)=1+2+~~+(n−1)=n(n−1)/2
​
0<=n(n-1)/2

(n) ∈ O(n^2)

Worst Case의 시간 복잡도는 O(n²) 이다.

average case(중간):

평균적으로 삽입할 위치는 중간 정도 → 약 (j-1)/2번 이동 -> 시그마 n=2 n까지 (j-1)/2
실행횟수 T(n)= n(n-1)/4

Average Case의 시간복잡도는 O(n²) 이다.

귀납증명

best는 n-1 worst는 n(n-1) / 2 average는 n(n-1) / 4 에서 n=1 대입, n=n-1일때 가정 후 양쪽이 같다는 것을 증명하면 된다.