junimnjw   2년 전

TC 에서 제대로 나오는 것 같고 문제가 없어보이는데 계속 틀렸다고 나오네요.. 혹시 어디가 문제일까요?

단순히 Heap Sort 만 사용해서는 안되는건가요?

고수님 도움 부탁드립니다. 

chogahui05   2년 전

네. 

Heap sort는 안정 정렬이 아닙니닷! Heap sorting 하실 때 proirity만 기준으로 위로 올리고 내리고 하신 거 같은데.

당연히 같은 우선순위라면 Top에 누가 먼저 올라오느냐에 따라서 순서가 달라지기 때문에

안정 정렬이 아니에요. 자세한 정보는 여기 봅시다~


https://stackoverflow.com/ques...

chogahui05   2년 전

의외로 빈도 정렬 같은 문제에서

테케는 맞는 데 왜 틀리나요? 라는 질문이 심심찮게 들어오는데요.

들어온 순서에 따라서. 그리고 정렬 후에도 우선순위가 같을 때, 상대적인 순서가 같은 게 보장된다. 

그러니까 stable하게 정렬이 된다면, 들어온 순서를 sort의 기준으로 안 써도 됩니다.

But. 그렇지 않은 경우 (ex. selection sort)

들어온 순서에 상관없이, 우선순위만 같다면 순서가 뒤바뀌어버릴수도 있기 때문에 


들어온 순서에 따라 정렬을 해야 한다.

그러면 기준을 '들어온 순서' 하나 더 추가해야 합니다.

Question.

c++의 stable_sort와 sort는 내부적으로 어떤 알고리듬으로 구현이 되어 있을까요?

이것도 알아보시면 좋을 거 같습니다.

댓글을 작성하려면 로그인해야 합니다.