[BaekJoon/백준] 10814번

나이순 정렬 문제다.

 

정렬 후에도, 값이 같은 원소의 전후관계가 바뀌지 않는 정렬 알고리즘을 안정 정렬(stable sort)이라고 한다.

 

안정정렬에 해당하는 병합정렬을 직접 구현해 풀었다.

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

typedef struct {
    
    int age;
    char name[101];
} person;

person *x;

void __merge_sort(person a[], int left, int right ){
    
    if(left < right) { // 요소 2개 이상일 경우
        int i;
        int j = 0;
        int p = 0;
        int k = left;

        int center = ( left + right ) /2;
        
        __merge_sort(a, left, center);
        __merge_sort(a, center+1, right);
        
        
        for(i = left; i <= center; i++) {
            x[p].age = a[i].age;
            strcpy(x[p].name, a[i].name);
            p++;
        }
        
        while(i <= right && j < p) {
                        
            if(x[j].age <= a[i].age) {
                a[k].age = x[j].age;
                strcpy(a[k].name, x[j].name);
                k++; j++;
            } else {
                a[k].age = a[i].age;
                strcpy(a[k].name, a[i].name);
                k++; i++;
            }
        }
        while(j < p) {
            a[k].age = x[j].age;
            strcpy(a[k].name, x[j].name);
            k++; j++; // 여기서 k++ 하나 빼먹어서 시간 많이 씀 ㅜ
        }
    }
}
void merge_sort(person a[], int n) {
    x = calloc(n, sizeof(person));
    
    __merge_sort(a, 0, n - 1);
}

int main() {
    person *p;
    int nx;
    
    scanf("%d", &nx);
    
    p = calloc(nx, sizeof(person));
    
    for(int i = 0; i <nx; i++) {
        scanf("%d %s", &p[i].age, p[i].name);
    }
    
    merge_sort(p, nx);
    
    for(int i = 0; i <nx; i++) {
        printf("%d %s\n", p[i].age, p[i].name);
    }
    
}

병합정렬을 직접구현해서 코드는 좀 길다.