[백준/10814/C] 나이순정렬

첫번째시도: 그저 단순히 qsort를 통해서 해결하였다.

문제점은, qsort가 불안정정렬(이미 있는 배열을 무작위로 섞은뒤 정렬)이기 때문에 단순히 나이값이 같을때 변환을 안시켜준다고 비교함수를 정의하면 qsort의 불안정성에 의해 같은 나이값 내에서 기존의 정렬이 깨져버릴수도 있다는 것이다.

(운이 좋으면 맞을수도 있다)

#include <stdio.h>
#include <stdlib.h>
typedef struct s{
    int age; char name[101];
}PEO;

int compare(const void *pa, const void *pb){
    const PEO *a= pa; const PEO *b= pb;
    if (a->age == b->age) return -1;
    return a->age - b->age;
}

int main(){
    int N; scanf("%d",&N);
    PEO arr[N];
    for(int i=0; i<N; i++){
        scanf("%d %s",&arr[i].age, arr[i].name);
    }

    qsort(arr, N, sizeof(PEO), compare);
    for(int i=0; i<N; i++){
        printf("%d %s\n",arr[i].age, arr[i].name);
    }   
}

 

결론 : 가입순서에 대한 기준을 세워서 결정론적으로 만들 수 있다. 앞으로 퀵소트를 쓸때는 기준값이 같을때 변환이 생길수 있다는 점을 생각하고 새로운 기준을 만들어야하는 것을 명심하자.

 

++첨언) 비교함수를 집합에 정의한다는것은 집합에 order을 정의하는 것과 같다.

집합론이나 해석학을 알고 있다면 친숙하겠지만 order의 성질이 깨지면 qsort 내부에서 예측되지 않은 동작이 생길 수 있으니 주의하자.

(order의 정의: https://ko.wikipedia.org/wiki/%EC%A0%84%EC%88%9C%EC%84%9C_%EC%A7%91%ED%95%A9)

(예를 들어, 두 값이 같을 때 0대신 -1을 내보낸다면 compare(a,b) =-1, compare(b,a)=-1, ordering의 본질이 깨져버림

그러니 두 값의 차이가 0이라면 두 데이터를 정렬할 수 있는 새로운 기준을 생각해보자, 차이가 없을때 두 데이터가 바뀌어도 상관없으면 그냥 그대로 빼도 상관없긴하다)

#include <stdio.h>
#include <stdlib.h>
typedef struct s{
    int age; char name[101]; int index;
}PEO;

int compare(const void *pa, const void *pb){
    const PEO *a= pa; const PEO *b= pb;
    if (a->age == b->age) return a->index - b->index;
    return a->age - b->age;
}

int main(){
    int N; scanf("%d",&N);
    PEO arr[N];
    for(int i=0; i<N; i++){
        scanf("%d %s",&arr[i].age, arr[i].name);
        arr[i].index = i;
    }

    qsort(arr, N, sizeof(PEO), compare);
    for(int i=0; i<N; i++){
        printf("%d %s\n",arr[i].age, arr[i].name);
    }   
}