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

#include <stdio.h>
#include <stdlib.h>

void insertion(int a[], int n)
{
    int i, j, k;
    for (i = 1; i < n; i++)
    {
        for (k = 0; k < n; k++)
        {
            printf(" %d ", a[k]);
        }
        printf("\n");
        int tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
        for (k = 0; k < j; k++)
            printf("   ");
        if (i != j){
            printf("^");
        }else
        {
            printf(" ");
        }
        
        for (k = j; k < i; k++)
            printf("---");
        printf("+");
        printf("\n");
    }
}

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;
}