randomized quick sort - 정말로 더 나은가?

알고리즘에 큰 하나의 축으로 생각되는 sorting 알고리즘( 물론 제 생각입니다)

이 sorting 에는 여러가지 방법들이 있고, 각 방법마다도 또 여러 방식으로 구현을 할 수가 있다.

일단 sorting을 보자면,

insertion

merge

selection

bubble

heap

counting

그리고 오늘 조금 의문점을 가진 quick sort등등....이 있다.

(위 사진들은 내용과 거의 상관이 없습니다.)

앞서 말한것과 같이 같은 정렬이라고 하더라도 구현방식이나 추가적인 기능은 가지각색이다.

quick sort의 경우는 worst case인 인풋을 고려한 randomized quick sort를 예로 들 수 있는데, 이 randomized에서 뭔가가... 이해가 가지 않는단 말이지......

이해가 가지 않는다는 것이 뭐, 알고리즘적으로 왜 그렇게 하는지, 어떻게 작동하는지에 대한 이야기가 아니라,

정말로 randomized 가 basic보다 나은가에 대한 고찰이 들었는데....

일반적으로 볼 때, (혹은 내 주변에 몇몇의 의견)  randomized를 적용하여 worst case를 "극뽀옥" 하였으니 전체적인 performance가 좀 더 좋아졌다고 볼 수 있는것 아니냐? 라는 답을 듣고 잠시 고민을 했다.

그래?

내가 생각하기에는 그다지 나아지지 않은것 같은데..... 오히려 안좋은 경우조차 있을지도 모르잖아?

너무 경솔하게 판단하는 것은 아닌지, 해당 근거가 충분한 상태에서 그런 결론을 내린것인지 의문이 끊임없이 남았다.

당시 수업은 알고리즘 수업이었는데 이 질문을 왜 교수님에게 하지 않았는지 항상 후회하는데.... 

수업은 끝났지만일단 찾아가서 물어봐야지.

그래도 여쭤보려면 최소한의 조사는 있어야하니까, 뭐가 좋은지 따져봐야지

그래서 따져보기로 했습니다.

---------------------------------------(링크예정)

(결과는 추후 추가하겠습니다.)