삽입정렬

자료구조: 일차원 배열

시간 복잡도: 

1. 배열이 완전히 정렬된 경우 : 첫번째로 마주치는 반복문만 돌고 끝남
2. 배열이 거의 정렬된 경우 : O(N)  -> 사전작업을 통해 배열을 거의 정렬된 상태로 만들어놓고 삽입정렬을 수행하면 굉장히 빨라진다! 이런 매력 때문에 다른 정렬을 사용하는 경우에도 가끔씩 삽입 정렬을 섞어서 사용하곤 한다.
3. 일반적인 경우, 최악의 경우 : O(N^2)

따라서 최선의 경우 O(N), 최악의 경우와 평균적인 경우 O(N^2)

"재귀적 성격"을 포함하며, 삽입 정렬이 제대로 정렬한다는 것을 "수학적 귀납법"으로도 증명할 수 있다.

삽입 정렬은 선택정렬보다 2.5배 정도 빠르고, 버블정렬보다 11배 정도 빠르다. ( 버블 < 선택 < 삽입 )

 

사용 목적 : 숫자의 오름차순 or 내림차순 정렬

#include <stdio.h>
#include <stdlib.h>
int main(){
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int arr_size = sizeof(arr) / sizeof(int);
    
    //mixing
    for(int i = 0; i < arr_size; i++){
        int temp = arr[i];
        int random_num = rand() % arr_size;
        arr[i] = arr[random_num];
        arr[random_num] = temp;
    }
    

    //sorting
    for (int i = 0; i < arr_size; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if(arr[j] > arr[i]) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    
    //print result
    arr_size = sizeof(arr) / sizeof(int);
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    

    return 0;
}