[Quick Sort] Quick sort는 왜 빠를까? (2) : 기대값을 고려한 Quick sort / Quick sort의 Expected running time /

Expected Running Time이란?

만약 동전을 100번 던진다고 치자. 우리는 앞면이 최대 100번 나올 수 있는 것을 당연히 알고 있다. 하지만, 또한 우리는 앞면이 평균 50번 정도가 나올 것도 알고 있다. 50번보다 조금 나올 때도 있을 것이고, 50번보다 많이 나오는 때도 있을 것이지만, 우리는 시행이 거듭될 수록, 50번에 수렴한다는 것을 직감적으로 알고 있다. 이 50이라는 숫자가 이 100번 던지는 시행의 기대값이다.  Quick Sort의 경우에도 우리가 정렬을 사용할 때를 적용하려면 최악의 경우가 아닌 이런 기대값 Running Time 이 중요할 것이다!

 

QuickSort 의 Expected Running Time 

앞서 말했듯이 input값이 랜덤한 값들로 들어온다고 했을때, 우리는 확률을 이용하여 QuickSort의 Running Time의 기대값을 구해볼 수 있다. 쉽게 말하자면, 무작위 값들이 들어왔을때, 실제로 일어나는 평균 시간이다. (기대값)

 

그렇다면 확률은 어떻게 구할까??

 

QuickSort 는 Partition 이라는 함수로 피벗 기준 크고 작은 두 개의 하위배열로 나눠준 뒤

재귀적으로 계속 나누어 붙여준 후 단순히 붙이는 방법을 쓰고 있다.

QuickSort 내부에 있는 Partition 함수를 들여다보자. 

피벗이 어떤 것으로 설정되냐에 따라 하위 배열은 달라질 것이다.  피벗이 계속해서 정확히 중간값으로 설정될 때 시간은 최소가 되고, 피벗이 계속해서 가장작은 값, 혹은 큰 값으로 설정되어 배열이 불균형하게 된다면 시간은 더 커질 것이다.

 

피벗이 불균형되면 왜 시간은 더 오래걸릴까?

Randomized quick sort에서는 피벗이 랜덤으로 결정된다고 가정한다. (랜덤 input으로 생각하기 때문)

[1 2 3 4 5 6 7] 중에 피벗이 4로 설정이 된다면?  [1 2 3]   4   [5 6 7]   로 나뉘어지게되고 재귀적으로

[1 2 3] 과 [5 6 7] 자체의 퀵소트가 시작되므로 더이상 [1 2 3] 과 [5 6 7] 은 비교를 할 필요가 없게된다.

 

반면에 피벗이 7로 설정이되면??  [1 2 3 4 5 6] 7   이 되어 [1 2 3 4 5 6] 의 퀵소트가 시작된다.

그렇게 되면 1 2 3 4 5 6 끼리의 비교의 필요성은 아직 남아있는 것이다. 계속해서 이런식으로 끝부분이 설정이되면 비교의 필요성이 는다!  비교를 계속해서 해준다는 것은 시간도 그만큼 오래 걸린다는 소리!!

 

비교 실행의 횟수

'한 원소가 다른 원소와 얼마나 비교가 되는지' 가 결국 퀵소트의 빠르기에 직결하기 때문에, 결국 우리는 비교 실행의 횟수에 주목할 필요가 있다. 아래 함수를 예시로 보면 if A[j] <= x 문이 얼마나 많이 쓰일지! 가 Running Time에 직결된다.

Partition 문은 최대 n번 실행되므로 만약 X를 비교의 총 횟수라 치면 O(n+X) 라고 할 수 있다.

그렇다면 비교의 횟수는 어떻게 계산할까???   

 

다음 게시글 Quick sort는 왜 빠를까? (3) : 비교 실행의 개수 계산'(https://programming119.tistory.com/74) 에서 이어진다...