冒泡排序比较和交换的总数

Question

我有这段用于 C++ 冒泡排序的代码。首先它生成随机数并将它们放入数组中。之后我调用我的 bubbleSort 函数，它进行排序。一切正常。但是我很好奇我怎样才能找到冒泡排序所做的一些总比较和数字交换？我创建了一个 CountBubbleSort 整数用于比较。但是我不确定我应该在代码的哪一部分增加它。我想在第一个循环内的第二个 for 循环之后添加它。希望你明白我的意思。对不对？比较次数定义了这个公式 n*(n-1))/2。对于交换，它是 3*(n-1)。但是我怎样才能将它实现到我的代码中呢？感谢大家的帮助。

void swap(double *xp, double *yp)
{
    double temp = *xp;
    *xp = *yp;
    *yp = temp;
}

double *Data;
double* A;
double n, temp;

void generate(int _n, const char *_file);
void read(const char *_file);   
void printArray(double arr[], int n); 
void bubbleSort(double arr[], int n);

int main()
{
    int m;
    int CountBubbleSort = 0;

    srand(time(NULL));
    cout << "Amount of random numbers you want: ";
    cin >> m;
    cout << "Generating random data ..." << endl;
    generate(m, "duom.txt");
    cout << "Reading data" << endl;
    read("duom.txt");
    A = new double[n];

    for (int i = 0; i < n; i++) {
        A[i] = Data[i];
    }

    cout << "Randomly generated array" << endl;
    printArray(A, n);

    // Bubble Sort
    bubbleSort(A, n);

    cout << "Array after bubble sort" << endl;
    printArray(A, n);

    return 0;
}

void bubbleSort(double arr[], int n)
{
    bool swapped;
    for (int i = 0; i < n - 1; i++)
    {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
        // Should I add CountBubbleSort += i here or not?
        if (swapped == false)
            break;
    }
}

void printArray(double arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << A[i] << endl;
    }
}

Answer 1

这是一个相对简单的更改：

在 if 语句之前增加比较计数
增加 if 语句中的交换计数器

取两个int&参数进行计数，像这样：

void bubbleSortCounted(double arr[], int n, int& countComparisons, int& countSwaps);

递增计数器的代码如下所示：

countComparisons++;
if (arr[j] > arr[j + 1])
{
    countSwaps++;
    swap(&arr[j], &arr[j + 1]);
    swapped = true;
}

来自 main() 的调用如下所示：

int cmp = 0, swp = 0;
bubbleSort(A, n, cmp, swp);
std::cout << cmp << " comparisons, " << swp << " swaps" << std::endl;

Answer 2

However I was curious how can I find a number of total comparisons and number swapping that bubble sort makes? I created a CountBubbleSort integer for comparisons. However I'm not sure in which part of my code should I increment it.

您的 bubbleSort() 函数中只有一行实际比较数组中的两个元素，因此按理说，如果您想计算比较元素的次数，您应该递增在比较发生之前或之后立即计数器。

冒泡排序比较和交换的总数

Bubble sort the total number of comparisons and swaps

c++

sorting

bubble-sort