병합 정렬에 대한 백분율 비교

Question

목록 정렬시 병합 정렬 알고리즘의 비교 횟수를 계산하려고합니다. 여러 가지 방법을 시도했지만 재귀 때문에 항상 목록의 크기 인 대답으로 반환됩니다. 이 비교의 수를 계산하는 방법에 대한 제안?

Answer 1

나는 두 가지 솔루션을 생각할 수 있습니다 :

적은 아름다운

1. 하지만 쉽게 구현 할 수 있습니다.

전역 변수로 카운터를 선언하십시오. global counter을 사용하여 함수에서 참조 할 수 있습니다.

<안녕, 시작 = "2">
2. 방지 전역 변수 여기

는 :

mergesort(lefthalf) 
mergesort(righthalf) 

당신은 반환 비교 카운터를 사용하지 않습니다. 너가 무언가를하면 :

count += mergesort(lefthalf) 
count += mergesort(righthalf) 

너는 비교 조사를 얻을 것이다. 전화 할 때마다 카운터를 0으로 초기화하십시오. mergesort()