<6> Q11. 자료구조와 함께 배우는 알고리즘 입문 (C언어)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void insertion(int a[], int n)
{
    int i, j;

    for (i = 1; i < n; i++)
    {
        int key = a[i];
        int pl = 0;
        int pr = i - 1;
        int pc;
        int pd;

        do
        {
            pc = (pl + pr) / 2;
            if (a[pc] == key)
                break;
            else if (a[pc] < key)
                pl = pc + 1;
            else
                pr = pc - 1;
        } while (pl <= pr);
        pd = (pl <= pr) ? pc + 1 : pr + 1;

        memmove(a + pd + 1, a + pd, sizeof(int) * (i - pd));
        a[pd] = key;
    }
}

int main(void)
{
    int i, nx;
    int *x;
    puts("단순 삽입 정렬");

    printf("요소 개수 : ");
    scanf("%d", &nx);
    x = calloc(nx, sizeof(int));

    for (i = 0; i < nx; i++)
    {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }

    insertion(x, nx);

    puts("오름차순으로 정렬했습니다.");
    for (i = 0; i < nx; i++)
        printf("x[%d] = %d\n", i, x[i]);

    free(x);

    return 0;
}