힙 배열 및 삽입 정렬의 복사 및 비교 횟수 계산

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; 

. 정수가 아닌 이중 비교에 대해 이야기한다고 가정하면 비교가 수행되거나 수행되지 않을 수 있습니다. 두 번째로 들여 쓰기가 너무 오도합니다. (당신 항상 증가.) 당신은

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

아마 다른 오류가 필요하지만, 내가 당신의 언어를 읽을 수 없기 때문에 말할 수 없다, 그래서 인쇄 된 텍스트, 주석, 그리고 이름은 의미가 .

당신이 C++로 글을 쓰고 있다면, operator <()과 operator =을 가진 클래스와 복사 생성자를 작성하고이를 계측 할 것입니다. 그렇게하면 이 잘못 될 수 있습니다.