알고리즘 고수분들 퀵소트 질문 하나 부탁드립니다

[익명(119.196)]

퀵소트 할 때 피벗값 좌우로 작은 애들, 큰 애들을 붙이잖아요

이때 가운데 피벗값을 하나만 박고 나머지 애들을 처리할때와

아니면 피벗값 및 같은 값들의 리스트를 박고 나머지 애들을 처리할때

어느 쪽이 더 효율적인가요??

[츄럴(rhdnfka94)]

다들 하스켈을 몰라서 무플 예상

[익명(119.196)]

제목을 수정할까요 ㅋㅋ 사실 하스켈인 건 별 상관없는 문제 같은데 ㅠㅠ

[츄럴(rhdnfka94)]

사실 글의 코드 설명을 먼저 봤는데 못알아들어서 코드를 봤더니 하스켈이라 포기..

[codesafer(codesafer)]

퀵소트를 쓴다면 동일한 값이 자주 등장하지 않는 경우에 쓴다고 봐야지. 그렇다면 당연히 전자가 유리.

[익명(223.38)]

큰 차이는 없음 다만 피봇을 가운데로 설정하면 피봇도 교환가능한 수이므로 추가적인 코드 필요

[codesafer(codesafer)]

그니까 소스코드 기준에선 qsort2 가 유리.

[익명(119.196)]

아 왜 해당 소트를 썼는지에 대한 고민부터 있어야겠군요... 감사합니다!

[츄럴(rhdnfka94)]

크~~~~

[익명(223.38)]

퀵소트는 언스테이블 소트라 중복값 있을때는 쓰면 안되

[익명(119.196)]

일단 언스테이블 소트라는 게 뭔지부터 공부해봐야겠군요... 프로그래밍 초보라 뭐가 뭔지 모릅니다 ㅠㅠ

[codesafer(codesafer)]

스테이블 언스테이블 문제는 여기서 고민할꺼리는 아니구~ 언스테이블일 경우에는 unique key 로 바꾸면 되니까 그건 별도로 다루는게 맞다.

[codesafer(codesafer)]

동일한 키값을 가질때 입력 순서를 유지하지 않는게 unstable 이지 뭐.

[codesafer(codesafer)]

즉, 비교할 key 값 + 일련번호 를 합쳐서 키로 잡으면 어떤 알고리즘이든 stable 해지는거지 뭐.