오늘은 퀵정렬이다.
퀵정렬은 정렬의 자존심이라고 한다.
그리고 pivot을 잡는 점에서 특이하다.
피봇을 잡는 방식이 크게 두가지로 나뉘는데,
(피봇을 어떻게 잡느냐에 따라 어떤 퀵정렬인지로 나뉠수 있음.)
랜덤방식과 한쪽 영역을 피봇으로 잡는 방식이 있다.
오늘은 맨 오른쪽에 피봇을 잡는 방식을 구현해보았다.
개인적으로 그렇게 막히는 부분은 없었다. (천천히 진행해서 그런가..?)
퀵정렬의 시간복잡도는
최하: O(n^2)
평균, 최상: O(nlogn)
를 가지는데,
오늘 구현한 맨 오른쪽을 피봇으로 지정한 퀵정렬은
재귀함수의 가장 깊은곳으로 빠지기때문에
어레이의 모든 엘리멘트를 비교하게되고, 최하의 속도를 나타낼 것이다.
github: https://github.com/jeong-jaehyeon/JavaProject/tree/guichetController
오늘의 코멘트: 병합정렬이랑 비슷하다는게 무슨말인지 대략 감은 오네
"돈받고 일하면 프로다"