Insertion Sort 1

삽입 정렬(insertion sort)은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다.

1.

* 성능

* Worst Case (역배열)

- 비교 연산 : (N * (N-1)) / 2 번
- 교환 연산 : (N * (N-1)) / 2 번
- 총 연산 : O (N^2)

* Best Case (정배열)

- 비교 연산 : N번
- 교환 연산 : 0번
- 총 연산 : O(N)​

* Average

- 총 연산 : O (N^2)

* 특징

- 역순일 때 최악이지만, 이미 정렬되어 있는 경우는 매우 빠름
- 난수 정렬이나, 대충 정렬된 배열의 경우 속도가 빠르다 (특히, 작은 개수의) -> Quick Sort 개선을 위해 쓰임
- 비교횟수가 적고, 교환횟수가 많다
- 안정성이 있다 (단, 비교 연산자가 >, < 인 경우!  = 연산자가 들어가면 안정성이 깨진다)

#include <stdio.h>
#include <malloc.h>

#define MAX 10

void insertion_sort(int arr[], int n) {

    for (int i = 1; i < n; ++i) {
        int j = i;
        int tmp = arr[i];

        while (j > 0 && arr[j - 1] > tmp ) {
            arr[j] = arr[j - 1];
            --j;
        }

        arr[j] = tmp;
    }
}

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

    insertion_sort(arr, MAX);

    print(arr, MAX);

    return 0;
}

* 출처 : https://brilliant.org/wiki/insertion/