ヒープソートと挿入ソートのコピーと比較の回数をカウントする

Question

アルゴリズムが何回比較を行い、何回アルゴリズムがコピーを行うのかをカウントしたい。

#include <stdio.h> 
#include <random> 
#include <fstream> 
#include <iostream> 
#include <algorithm> 
#include <time.h> 


void generuoti(int _N, const char *_file); 
void nuskaityti(const char *_file); 
int ps = 0; 
int ks = 0; 
void heapify(double arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2 * i + 1; // left = 2*i + 1 
    int r = 2 * i + 2; // right = 2*i + 2 


    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
     largest = l; 
     ps+=1; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
     largest = r; 
     ps += 1; 
    // If largest is not root 
    if (largest != i) 
    { 
     std::swap(arr[i], arr[largest]); 
     ps += 1; 
     ks += 1; 
     // Recursively heapify the affected sub-tree 
     heapify(arr, n, largest); 
    } 
} 

// pagr funkcija haep sortui 
void heapSort(double arr[], int n) 
{ 
    // Build heap (rearrange array) 
    for (int i = n/2 - 1; i >= 0; i--) 
     heapify(arr, n, i); 

    // One by one extract an element from heap 
    for (int i = n - 1; i >= 0; i--) 
    { 
     // Move current root to end 
     std::swap(arr[0], arr[i]); 
     ks+=1; 

     // call max heapify on the reduced heap 
     heapify(arr, i, 0); 
    } 
} 

void insertion_sort(double arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++) 
    { 
     key = arr[i]; 
     j = i - 1; 
     ks+=1; 

     while (j >= 0 && arr[j] > key) 
     { 
      arr[j + 1] = arr[j]; 
      j = j - 1; 
      ks+=1; 
      ps+=1; 
     } 
     arr[j + 1] = key; 
      ks+=1; 
    } 
} 

using namespace std; 

double *Data; 
double* A; 
double* B; 
double N; 



int main() 
{ 
    srand(time(NULL)); 
    cout << "Generuojame atsitktinius duomenis" << endl; 
    generuoti(20000, "duom.txt"); 
    cout << "Nuskaitome duomenis" << endl; 
    nuskaityti("duom.txt"); 
    A = new double[(int)N]; 
    B = new double[(int)N];//jeigu algoritmui reikia papildomo masyvo 
    for (int i = 0; i < N; i++) { 
     A[i] = Data[i]; 
    } 

    cout << "Pradine skaiciu seka:" << endl; 
    for (int i = 0; i < N; i++) 
     cout << A[i] << " "; 
    cout << endl; 
    // 


    insertion_sort(A, N); 
    //heapSort(A, N); 

    //truksta veiksmu sk 
    cout << "Surusiuota skaiciu seka:" << endl; 
    for (int i = 0; i < N; i++) 
     cout << A[i] << " "; 
    cout << endl; 
    cout << "Kopijavimu skaicius " << ks << endl; 
    cout << "Palyginimu skaicius " << ps << endl; 
    system("pause"); 
    return 0; 
} 

void generuoti(int _n, const char *_file) { 
    ofstream os(_file); 
    os << _n << endl; 
    for (int i = 0; i<_n; i++) 
     os << " " << 500+ (double)(rand() % 3001) ; 
    os.close(); 
} 

void nuskaityti(const char *_file) { 
    ifstream is(_file); 
    if (is.fail()) { 
     cout << "Failo nera" << endl; 
     exit(1); 
    } 
    is >> N; 
    Data = new double[(int)N]; 
    for (int i = 0; i < N; i++) { 
     is >> Data[i]; 
    } 
} 

これは私のコードであり、ps - は比較の数に等しく、ks - はコピー回数に等しい。アルゴリズムですべての比較とすべてのコピーを数えたかどうか尋ねたいと思いますか？答えをありがとう。

Answer 1

ん

if (l < n && arr[l] > arr[largest]) 
     largest = l; 
     ps+=1; 

二つの問題がここにあります。整数（整数ではなく）の二重の比較について話していると仮定すると、比較が行われる場合と行われない場合があります。 第2に、あなたのインデントは深刻な誤解を招くことです。 （あなた常にインクリメント。） あなたは

if (l < n) { 
     ps++; // About to compare 
     if (arr[l] > arr[largest]) 
      largest = l; 
    } 

は、おそらく他のエラーがある必要がありますが、私があなたの言語を読み取ることができないので教えすることは不可能なので、印刷されたテキストは、コメント、名前は無意味です。

あなたがC++で書いているとすれば、私はoperator <()とoperator =のクラスとコピーコンストラクタを作成し、それらを計器にします。そうすれば、はおそらくになります。