[C] <자료구조> 삽입 정렬 알고리즘 insertion sort 시간 복잡도

삽입 정렬

삽입 정렬은 한 번에 한 항목씩 최종 정렬된 배열에서 자신의 위치를 찾아 삽입함으로 정렬을 완성하는 알고리즘이다.

시간 복잡도는 평균 O(n²)으로 퀵 정렬이나, 힙 정렬 또는 병합 정렬과 같은 고급 알고리즘보다 큰 목록에서 비효율적이다.

시간 복잡도의 최상은 O(n), 최악은 O(n²)이다.

다음 영상은 삽입 정렬의 동작 방식이다.

#include <stdio.h>
void insertion_sort(int arr[], int len) {
    for (int i = 1; i < len; i++) {
        int key = arr[i];
        int j;
        for (j = i - 1; j >= 0 && key < arr[j]; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j+1] = key;
    }
}
int main() {
    int arr[] = { 9,1,8,4,3,5,2 };
    int len = sizeof(arr) / sizeof(int); //배열의 길이
    insertion_sort(arr, len);
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
}