삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort) - O(N2)

모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하여 정렬

정위치에 삽입해야 하므로 기존에 있었던 원소를 뒤로 밀어주어야 합니다. 

※ 대부분의 원소가 이미 정렬되어 있는 경우에는 효율적이지만, 그렇지 않은 경우 빈번한 이동 발생

　

 

[C 언어] - 오름차순 기준

# include <stdio.h>

int swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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

void main() {
    int n = 10;
    int arr[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
    
    insertionSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
}

 

Reference

▶ 정렬 알고리즘 비교