C Data Structure - 삽입 정렬

삽입 정렬 어렵진 않은데 뭔가 설명을 적기에는 복잡하다 휴 영상이면 좋을텐데 말이지

일단 기록해둔다.

삽입 정렬이란?

삽입해서 정렬하는 것이다. 예를 들어서 

이와 같은 배열이 있을 때, 아래의 그림 순으로 설명하겠다.

그림으로 설명을 좀 대체했다. 나중에 알아먹을 수 있을란가 모르겠군.

그리고 각 그림 속 번호는 그림을 처음 봤을 때 읽어야 할 순서의 동글뱅이 번호를 뜻한다.

코드 및 결과

----

#include <stdio.h>
 
void InsertSort(int arr[], int n)
{
    int i = 0, j = 0;
    int target_value = 0;
 
    for (i = 1; i < n; i++) // 각 i가 조정할 타겟이 된다.
    {
        target_value = arr[i]; // 삽입할 target value를 따로 저장한다.
        for (j = i-1; j >= 0; j--)
        { // 역순으로 가는 것이니 j가 j+1 보다 먼저이며 앞에서 뒤로 땡기는 행위를 할 것이다.
            if (arr[j] > target_value) // 앞에 것과 비교했을 때 값이 크면 오름차순 위배 
                arr[j+1] = arr[j]; // 뒤로 땡긴다.
            else // 오름차순에 맞으므로 
                break; // 일단 반복문 하나를 탈출하고,
        }
        arr[j+1] = target_value; // 방금 비교한 앞에 요소(arr[j]) 바로 뒤에 빈 공간에 대입
    }
    
    return;
}
 
int main(void)
{
    int i = 0;
    int arr[4] = { 3, 5, 9, 1 };
    InsertSort(arr, sizeof(arr) / sizeof(int));
    
    for (i = 0; i < 4; i++)
        printf("%d, ", arr[i]);
    fputc('\n', stdout);
    return 0;
}

----

 

삽입 정렬 성능

이미 정렬되어있는 부분들이 많을수록 성능은 좋다.

최악의 경우 비교, 대입 횟수는 버블 정렬과 마찬가지로 O(n^2) 이다
왜냐하면 안쪽, 바깥쪽 반복의 횟수가 일치하기 때문이다.

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)