삽입정렬

의미>​

선택정렬은 한 번 반복 할 때에 타겟이 되는 대상들을 모두 비교하여 min인 경우 무조건 min 값을 챙겨놨다가 인덱스를 하나 하나 움직이면서 챙겨둔 min 값을 넣는 것.

버블정렬은 인접한 원소와 비교하여 조건절이 만족하면 무조건 이를 위치를 바꾸어서 배열의 끝 혹은 맨 앞에 적재 하는 것.

삽입정렬은 버블정렬과 유사한 측면이 있지만 "필요할 때에만" 위치를 바꾼다는 점에서 조금 다르다. 즉, 버블정렬은 인접한 두 원소를 인덱스를 증가시키면서 계속 비교하고 계속 가져가던 원소가 조건에 부합하면 그거때문에 위치를 바꾸고 새로 만난 원소가 더 적절하면 그것을 다시 가지고 가면서 위치를 바꾼다.

반면, 삽입정렬은 기존의 정렬이 "이미 되어있다"고 가정을 한 상태에서 인덱스를 증가시키기 때문에 조건절을 만족 할 때에만 위치를 바꾸고 그 외에는 비교 연산만 들어간다. 따라서 같은 시간복잡도라 할 지라도 연산이 덜 들어간다고 한다.

​​

코드예시>

#include <stdio.h>

// 삽입정렬
int main(void){
    
    int i, j, temp;
    int array[10] = {5, 7, 8, 9, 4, 6, 1, 3, 2, 10};

    for(i = 1; i < 10; i ++){

        for(j = i; j > 0; j--){
            
            if(array[j] < array[j - 1]){
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }

        }

    } // end-for

    for(i = 0; i < 10; i++){
        printf("%d ", array[i]);
    }

}

​

시간복잡도>

​

N(N+1)/2

-> N^2/2 + N/2

-> N^2/2

-> N^2

= O(N^2)