[C] 백준 2750번: 수 정렬하기

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

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

typedef struct Node
{
    int val;
    struct Node *next;
} Node;

// Get minNode whose next node is min in linked list
Node *getMinNode(Node *header, int length)
{
    Node *cur = header;
    Node *minNode = cur;

    for (int i = 0; i < length; i++)
    {
        if (cur->next->val < minNode->next->val)
            minNode = cur;

        cur = cur->next;
    }

    return minNode;
}

Node *doSelectionSort(int N, Node *header)
{
    int i;
    Node *newHeader = malloc(sizeof(Node));
    Node *newLast = newHeader;

    for (i = 0; i < N; i++)
    {
        Node *minNode = getMinNode(header, N - i);

        // Move item, set newLast
        newLast->next = minNode->next;
        minNode->next = minNode->next->next;
        newLast = newLast->next;
    }

    return newHeader;
}

Node *getPrevNode(Node *header, int length, int val)
{
    int i;
    Node *cur = header;
    for (i = 0; i < length; i++)
    {
        if (cur->next->val > val)
            break;

        cur = cur->next;
    }

    return cur;
}

Node *doInsertionSort(int N, Node *header)
{
    int i;
    Node *newHeader = malloc(sizeof(Node));
    Node *cur = header->next;

    for (i = 0; i < N; i++)
    {
        Node *prevNode = getPrevNode(newHeader, i, cur->val);
        Node *next = cur->next;

        cur->next = prevNode->next;
        prevNode->next = cur;

        cur = next;
    }

    return newHeader;
}

int main()
{
    // Input
    int i;
    int N;
    scanf("%d", &N);

    // Header
    Node *header = malloc(sizeof(Node));
    Node *last = header;

    for (i = 0; i < N; i++)
    {
        Node *newNode = malloc(sizeof(Node));
        scanf("%d", &newNode->val);

        last->next = newNode;
        last = newNode;
    }

    // Solution & Free
    Node *cur = doInsertionSort(N, header)->next;
    for (i = 0; i < N; i++)
    {
        Node *next = cur->next;
        printf("%d\n", cur->val);
        free(cur);
        cur = next;
    }
    free(header);

    return 0;
}

알고리즘 수업의 PPT에서 소개된 Selection Sort, Insertion Sort의 구현입니다.

C언어를 복기하기 위함입니다.