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

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

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

9장 Exercise 문제다.

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

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

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

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

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

#include <stdio.h>
#include <stdlib.h>
#define SWAP(a,b) {int t; t=a; a=b; b=t;}
 
void PrintArray(int list[], int sorted, int n, int before)
{
    int unsorted = n - sorted;
 
    printf("(");
    for (int i = 0; i < sorted; i++)
    {
        if (i == sorted - 1)
            printf("%d", list[i]);
        else
            printf("%d, ", list[i]);
    }
    printf(")   ");
    if (sorted > 0 && sorted < n)
        printf("  ");
 
    printf("(");
    for (int i = sorted; i < n; i++)
    {
        if (i == n - 1)
            printf("%d", list[i]);
        else
            printf("%d, ", list[i]);
    }
    if (unsorted == 0)
        printf(")");
    else
        printf(")");
 
 
    if (before == -1)
        printf("%9c초기 상태\n", ' ');
    else
        printf("%9c%d 선택 후 %d 교환\n", ' ', list[sorted-1], list[before]);
}
void SelectionSort(int list[], int n)
{
    int i=0, j;
    int minidx = -1;
 
    PrintArray(list, i, n, minidx);
    for (i = 0; i < n-1; i++)
    {
        minidx = i;
        for (int j = i+1; j < n; j++)
            if (list[minidx] > list[j])
                minidx = j;
        SWAP(list[i], list[minidx]);
        PrintArray(list, i+1, n, minidx);
    }
    PrintArray(list, i + 1, n, n - 1);
}
 
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]);
 
    SelectionSort(ar, n);
    
    free(ar);
    return 0;
}