Insertion Sort

Insertion Sort

void insertionSort(int arr[], int n){
    int tmp;
    int idx;
 
    for(int i=1;i<n;++i){
        tmp = arr[i];
        idx = i-1;
        while(idx >= 0 && arr[idx] > tmp){
            arr[idx+1] = arr[idx];
            --idx;
        }
 
        arr[idx+1] = tmp;
    }
}

• 삽입 정렬은 평균, 최악의 시간복잡도가 O(n^2) 로 버블, 선택 정렬과 같이 느리지만 직관적인 알고리즘으로 여겨지지만,
  최선의 경우 O(n)이기도 하며, 전체적으로 위 두 알고리즘보다 빠른 정렬기법이다.
• 배열의 인덱스가 0부터 시작될 때, 1 ~ n-1 라운드가 진행되며, i 라운드에 i 번째 원소의 위치를 찾는다.
  이 때, 0 ~ i 인덱스까지의 요소들은 정렬되어 있다고 가정하며 역순으로 탐방하며 자신의 위치를 찾아 들어간다.
  위 성질 때문에, 이미 원소가 정렬되어 있는 경우 즉, 최선의 경우 매 라운드마다 한번의 비교만을 거쳐 다음 라운드로 넘어가기 때문에
  O(n) 시간 복잡도를 지닐 수 있다.
• in-place 정렬이므로 공간복잡도는 O(n) 이다,