计算堆排序和插入排序中的复制和比较次数

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 =的类，以及一个复制构造函数，并对其进行检测。这样你就不可能弄错了。