std :: stable_sort로 해결했습니다

std::pair는 그 자체로 first끼리 비교한 후, 둘이 같으면 second를 비교하는 비교 함수를 가지고 있습니다.

그렇다면 구조체로 std:: sort 돌렸을 때는 unstable sort 인데 왜 pair로 std::sort를 돌렸을 때는 stable sort 인가요??

unstable sort랑 sort랑 헷갈려 하시는 거 같아요.

보통 sort라고 하면, 사용자가 정한 rank에 따라서 데이터를 다시 끼워 맞추는 일 정도라고 생각하시면 됩니다.

그렇기 때문에, 보통.. struct가 있는 경우에..

어떻게 정렬시킬거니? 라는 정보를 전달시켜 주는 거고요. 

ex. 성적순, 성적이 같다면 이름순으로 정렬하라.

이 때 정렬 기준은 밑줄 친 부분이 되겠네요.

pair 같은 경우, 그 자체로 first끼리 비교한 후, 둘이 같으면 second를 비교하는 비교 함수를 가지고 있다.

여기서 sorting 기준은, first끼리 비교하고, 둘이 같으면 second끼리 비교한다는 겁니다.

즉, first가 작고, first가 같으면 second가 작은 쪽이 앞에 나온다. 라는 기준을 가지고 있어요. 그 기준에 따라서 정렬하는 것 뿐입니다.

stable이냐, unstable이냐가 나오려면..

같은 우선순위를 가지는 데이터가 있을 때, 순서가 바뀌지 않음이 보장되느냐. 그렇지 않은가? 입니다. pair랑은 아무런 관계가 없어요.

pair가 정렬 기준을 2개 두는 것 뿐이고. 애초에 sort()를 부르면 stable한 걸 부르지 않습니다. unstable 합니다.

kwj씨 코드를 봅시다.

struct st{int num,index;};

bool cmp(const st &a,const st&b)

{

    return a.num<b.num; //num이 작은 쪽이 앞에 와야 한다.

}

정렬 기준은 num이에요. 제가 밑줄 친 부분이고요. 이 야기는

어떤 원소 A와 B가 있다. A.num과 B.num이 같다면. A와 B의 상대적인 순서가 보장이 안 된다는 소리가 됩니다. unstable 하다면..

사실 정렬 후에 A - B순으로 와도 할 말이 없는 거고, B - A순으로 와도 할 말이 없는 것이지요.

만약에

bool cmp(const st &a,const st&b)

{

    if(a.num!=b.num) return a.num<b.num; //num이 다르다면 작은 게 앞에

    return a.index<b.index; //num이 같다면 index가 작은 게 앞에.

}

이렇게 바꾸면 어떻게 될까요? 기준이 2개가 생겨버려요. 설령, num이 같다고 해도.

뒤에 오는 index 값에 따라서 상대적인 위치가 결정되어 버립니다. sort에 대한 개념을.. 혼동하고 계신 거 같은데.

차근 차근 잘 정리해 보시면 좋을 거 같습니다. 상당히 어렵지만.. 생각 외로 중요하고. 간과하고 넘어갈 수 없는 주제라.

꼭 짚고 넘어가셨으면 좋겠습니다.

자체적으로 stable sort가 된 게 아니라 두 번째 원소에 처음의 인덱스 i를 저장해 두시니까, 이게 2차적인 기준이 된다면 당연히 첫 번째 원소가 같다면 처음의 순서가 그대로 유지될 수밖에 없겠죠. 제가 쓴 댓글의 의미를 잘 생각해 보세요.

stable sort (값이 같은 원소에 대해 처음의 순서를 유지) = unstable sort + 처음의 인덱스 값으로 2차 정렬 규칙 만들기

chogahui님 글 잘 읽어보았습니다. 

제가 간과한 경우가 있었군요. chogahui님 께서 말씀하신대로 2번째인자 index에 대해서 정렬을 안해서 생긴 문제였네요.

djm 님 말씀대로 index를 구조체변수의 두번째 인자로 설정했기에 2번째 인자에 대한 정렬기준만 제공하면 stable의 여부는 중요하지 않은것 같습니다.

저는 sort정렬과정에서 퀵소트로 정렬시 unstable 하게 정렬되서 발생하는 문제인줄 알았는데 댓글을 보고 글을 읽어보니 그게 아니었네요

두분의 명확한 지적 감사드립니다.