오늘은 퀵정렬_랜덤피벗 을 할 차례다.
그렇지만 오늘은 몸 컨디션이 별로 안좋은 관계로.. 간단하게 셋팅만 하고 개념알아보고 마무리 할 예정이다.
[랜덤피벗의 움직임]
랜덤 피벗은 평균적인 속도를 보여주고, 최악인 경우는 한쪽으로 치우친 경우, 최상의 경우는 중간 지점을 피벗으로 잡을 때.
랜덤 피벗은 한쪽으로 치우친 피벗의 단점을 보완한 경우이다.
이상적인 피벗을 기준으로 균등하게 나눠졌을 때
오름차순 또는 내림차순일 경우
실제로 JAVA에서 Arrays.sort() 내부적으로 [Dual Pivot Quick Sort]로 구현되어 있을 정도로 효율적인 알고리즘이라고 한다. 또 기술 면접에서 정말 빈번하게 나오는 주제이므로 반드시 숙지하는 것이 좋다고 한다.
내일은 구현을 진행하고, 왜 랜덤피벗이 한쪽 피벗의 단점을 보완한 것인가에 대해서 알아보겠다.
오늘의 코멘트: 컨디션 저하..