c++

如何测试c++快排函数的正确性

小樊
83
2024-08-28 00:40:44
栏目: 编程语言

要测试C++快速排序(Quick Sort)函数的正确性,可以遵循以下步骤:

  1. 编写一个快速排序函数:首先,你需要实现一个快速排序算法。这是一个简单的快速排序实现:
#include<iostream>
#include<vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j]< pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low< high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
  1. 创建测试用例:为了验证快速排序函数的正确性,你需要创建一些测试用例。这些测试用例应该包括不同类型的输入数组,例如已排序数组、逆序数组、具有重复元素的数组等。
vector<vector<int>> test_cases = {
    {1, 2, 3, 4, 5},
    {5, 4, 3, 2, 1},
    {1, 3, 5, 2, 4},
    {1, 1, 1, 1, 1},
    {1, 2, 3, 2, 1},
    {}, // 空数组
};
  1. 编写测试函数:编写一个测试函数,用于检查快速排序函数是否按升序对数组进行排序。
bool isSorted(const vector<int>& arr) {
    for (size_t i = 1; i < arr.size(); i++) {
        if (arr[i - 1] > arr[i]) {
            return false;
        }
    }
    return true;
}
  1. 运行测试:遍历所有测试用例,对每个用例调用快速排序函数,并使用测试函数检查结果。
int main() {
    for (auto& test_case : test_cases) {
        quickSort(test_case, 0, test_case.size() - 1);
        if (!isSorted(test_case)) {
            cout << "Test case failed: ";
            for (int num : test_case) {
                cout<< num << " ";
            }
            cout<< endl;
        } else {
            cout << "Test case passed."<< endl;
        }
    }
    return 0;
}
  1. 分析结果:运行上述代码,观察输出结果。如果所有测试用例都通过,那么你的快速排序函数应该是正确的。如果有任何失败的测试用例,请检查快速排序函数以找到错误并修复它。

0
看了该问题的人还看了