역시 단점을 보완한건 더 복잡하다.
랜덤 피벗 난수 선언, 하나의 임시 저장공간을 이용한 로직 추가.
정렬 알고리즘을 지난 며칠동안 계속해서 봐와서 그런가 막 그렇게 어렵진 않았지만 최근 진행했던 알고리즘 중에서는 헷갈린 편이였다.
(지정 피벗 퀵정렬에서 추가된 느낌이여서 그나마 할만했던듯+ 시간도 더 걸림 ㅠㅠ)
실제로 한쪽 지정 피벗 퀵정렬의 단점을 랜덤 피벗이 얼마나 보완하였나 확인하려고 swap할때마다 횟수를 확인해보니, (원소 4개 추가 후)
확연한 차이점을 보았다.
한쪽 지정 피벗 퀵정렬의 경우
64번을 고정적으로 도는 반면에,
랜덤 피벗 퀵정렬은
이외에도 20~40대까지의 경우의 수를 볼 수 있었다.
단지 어레이에 4개만 더 추가되었을 뿐인데 이정도로 늘어난다면 랜덤 피벗을 무조건 써야한다.
때문에 java에서도 채택해서 쓰는 것이겠지.
github: https://github.com/jeong-jaehyeon/JavaProject/tree/guichetController/src
오늘의 코멘트: 2020년이 끝나간다..
"돈받고 일하면 프로다"