DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 1

DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 1

C언어로 쉽게 풀어쓴 자료구조

9장 Exercise 문제다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.

19. 삽입 정렬의 코드를 수정하여 삽입 정렬의 각 단계를 출력하도록 하라. 아래 그림에서 왼쪽 괄호 안에 있는 숫자는 정렬이 되어 있는 숫자들이다. 오른 쪽은 정렬을 해야 할 숫자들이다. 삽입 정렬의 단계에서 다음과 같이 출력하도록 insertion_sort 함수를 수정하라. 이를 위하여 사용자로부터 숫자를 입력받을 수 있도록 하여라.

#include <stdio.h>
#include <stdlib.h>
 
void InsertionSort(int arr[], int n)
{
    int key;
    int i = 0, j;
 
    for (i = 0; i < n; i++)
    {
        printf("(");
        for (j = 0; j < i; j++)
        {
            if (j == i - 1)
                printf("%d", arr[j]);
            else
                printf("%d, ", arr[j]);
        }
        printf(")   ");
        if (i != 0)
            printf("  ");
 
        printf("(");
        for (j = i; j < n; j++)
        {
            if (j == n - 1)
                printf("%d", arr[j]);
            else
                printf("%d, ", arr[j]);
        }
        printf(")");
        if(i!=0)
            printf("%10d 삽입", key);
 
        key = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > key; j--)
            arr[j + 1] = arr[j];
        arr[j + 1] = key;
 
        printf("\n");    
    }
 
    printf("(");
    for (j = 0; j < i; j++)
    {
        if (j == i - 1)
            printf("%d", arr[j]);
        else
            printf("%d, ", arr[j]);
    }
    printf(")   ");
 
    printf("(");
    for (j = i; j < n; j++)
    {
        if (j == n - 1)
            printf("%d", arr[j]);
        else
            printf("%d, ", arr[j]);
    }
    printf(")");
    printf("%10d 삽입\n", key);
}
int main(void)
{
    int n;
    int *ar;
 
    printf("배열의 크기 : ");
    scanf_s("%d", &n);
 
    printf("배열 내용 입력 : ");
    ar = (int*)malloc(sizeof(int)*n);
    for (int i = 0; i < n; i++)
        scanf_s("%d", &ar[i]);
 
    InsertionSort(ar, n);
 
    free(ar);
    return 0;
}