워스트가 nlogn에 가까운 퀵소트를 어찌구현함?

[익명(218.148)]

pivot을 median에 가깝게 선택하면 된다

이렇게 던져주고 하라는데 아니 그걸 누가 모름...

[cc(221.155)]

퀵소트 피봇선택 알고리즘이 약간 몬테카를로 방식이랑 비슷하지 않냐? 랜덤에 기반해서 적당한 퍼포먼스를 내는 알고리즘. 퀵소트는 워스트 케이스가 n^2인 알고리즘이라 입력값에 대한 추가정보가 없으면 완전한 nlogn은 불가능

[asdf(104.10)]

피봇을 랜덤으로 선택하면 최악에 O(n^2) 이지만 확률상 거의 불가능함. deterministic 하게 median selection (O(n) 알고리즘) 알고리즘으로 피봇을 구하면 최악의 경우도 O(n log n)임.

[asdf(104.10)]

단 랜덤으로 피봇을 구하는게 성능상 훨씬 더 좋기 때문에 이걸 더 많이 사용하지.