Quick Sort1
[알고리즘] Quick sort는 왜 빠를까? (3) : 비교 실행의 개수 계산
비교의 수 가 곧 시간이다 전 게시물까지 내린 결론은 퀵 소트의 실행 시간은 서로 다른 두 원소가 얼마나 직접적으로 비교가 되느냐에 직결된다는 것이었다. 퀵 소트의 피벗은 랜덤으로 결정된다고 가정하였으므로, 랜덤 피벗에 따라 서로 다른 두 원소가 얼마나 비교되는지가 결정된다! 비교될 확률 i~j 까지 원소들 Z_ij 가 있을 때 원소 , z_i 와 z_j 가 비교될 확률을 구해보자. 만약 피벗이 i < p < j 인 p로 설정이 된다면, i 와 j 는 p 랑만 비교가 된 후 서로 다른 두 하위문제로 넘어가는 경우이다. 따라서 피벗이 i 혹은 j 로 설정 돼었을 때 X_ij = 1 이다. 따라서 Pr{z_i is compared to zj} = 2 / j-i+1 (i~j 까지의 개수) 이다. 최종 비교시간..