要測試C++快速排序(Quick Sort)函數的正確性,可以遵循以下步驟:
#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);
}
}
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},
{}, // 空數組
};
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;
}
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;
}