число сравнений срединный quicksort

Question

Как вычислить количество сравнений в медианном быстром сортировке? Где я должен увеличивать счетчик, чтобы вычислить это? Мой код срединной быстрой сортировки ниже:

void my_swap(vector<int>&vect, int dex1, int dex2) { 
    int temp = vect[dex1]; 
    vect[dex1] = vect[dex2]; 
    vect[dex2] = temp; 
} 
int find_median(vector<int>&vect, int p, int r) { 
    int center = (p + r)/2; 
    if (vect[p] > vect[center]) 
     my_swap(vect, p, center); 
    if (vect[p] > vect[r]) 
     my_swap(vect, p, r); 
    if (vect[center] > vect[r]) 
     my_swap(vect, center, r); 
    my_swap(vect, center, r - 1); 
    return vect[r - 1]; 
} 
void standart_sort(vector<int>&vect, int p, int r) { 
    if (r - p + 1 <= 1){ 
     return; 
    } 
    if (r - p + 1 == 2) { 
     if (vect[p] > vect[r]){ 
     my_swap(vect, p, r); 
     } 
     return; 
    } else { 
     if (vect[p] > vect[r - 1]){ 
     my_swap(vect, p, r - 1); 
     } 
     if (vect[p] > vect[r]){ 
     my_swap(vect, p, r); 
     } 
     if (vect[r - 1] > vect[r]){ 
     my_swap(vect, r - 1, r); 
     } 
    } 
} 
int partition_for_median(vector<int>&vect, int p, int r, double pivot) { 
    double x = pivot; 
    int i = p - 1; 
    for(int j = p; j <= r - 1; j++) 
    { 
     counter++; //pasted here 
     if(vect[j] <= x) 
     { 
     i++; 
     my_swap(vect, i, j); 
     } 
    } 
    my_swap(vect, i + 1, r); 
    return i; 
} 
void quick_sort_median(vector<int>&vect, int p, int r) { 
    if (r - p + 1 <= 3){ 
     counter2++; 
     standart_sort(vect, p, r); 
    } 
    else { 
     double median = find_median(vect, p, r); 
     int partition = partition_for_median(vect, p, r, median); 
     quick_sort_median(vect, p, partition - 1); 
     quick_sort_median(vect, partition + 1, r); 
    } 
} 

Например, в этом массиве {3,7,5,1,9,6,4,10,8,2} есть 25 сравнения, но как я могу вычислить, что?

Answer 1

Вы можете использовать пользовательскую функцию сравнения, которая выполняет обычное целочисленное сравнение, а также увеличивает глобальный счетчик. Аналогичная идея состоит в том, чтобы обернуть int в пользовательский класс с помощью собственной функции сравнения, выполняющей нечто подобное. Класс будет иметь статический счетчик.

Более хакерский способ - сделать прибор непосредственно в коде. Найдите каждое место в своем коде, где происходит сравнение, и увеличивайте счетчик.