不正确的比较和交换计数器输出用于快速排序功能

Question

我目前正在尝试实现一个c ++程序，该程序比较各种不同排序方法中的交换和比较次数。该程序似乎适用于所有排序方法(选择排序、插入排序(，但快速排序除外，无论列表的数据大小或顺序如何，它都只输出比较和交换计数 0。我在下面包含了完整的程序。快速排序函数肯定在工作，它唯一的计数元素并不奇怪，因为它使用外部比较和交换函数，旨在每次调用它们时增加适当的计数器。任何帮助将不胜感激。

#include <cstdlib>
#include <getopt.h>
#include <iostream>
#include <string>
#include<limits>
using namespace std;
unsigned long long comparisons = 0;
unsigned long long swaps = 0;
bool comp_less(int a, int b){
++comparisons;
if ( comparisons == std::numeric_limits<unsigned long long>::max() )
{
std::cout << "Number of comparisons reached max value. Resetting it 0.n";
swaps = 0;
}
return a < b;
}
void swap(int& a, int& b)
{
++swaps;
if ( swaps == std::numeric_limits<unsigned long long>::max() )
{
std::cout << "Number of swaps reached max value. Resetting it 0.n";
swaps = 0;
}
int t = a;
a = b;
b = t;
}
void selectionSort(int *first, int *last)
{
for(int *i = first; i < (last - 1); ++i){
int *min = i;
for(int *j = i + 1; j < last; ++j){
if(comp_less(*j, *min)){
min = j;
}
}
swap(*i, *min);
}
}

void insertionSort(int* first, int* last)
{
for (int *i = first + 1; i < last; ++i)
{
int temp = *i;
int *j;
for (j = i; j > first && comp_less(temp, *(j - 1)); --j)
{
swap(*j, *(j - 1));
}
*j = temp;
}
}
int *partition(int *first, int *last)
{
int *pivot = last - 1;
int *i = first;
int *j = last - 1;
for (;;)
{
while (comp_less(*i, *pivot) && i < last)
{
++i;
}
while (*j >= *pivot && j > first)
{
--j;
}
if (i >= j)
break;
swap(*i, *j);
}
swap(*(last - 1), *i);
return i;
}
void quickSort(int* first, int* last) {
{
if ((first - last) <= 1)
return;
int *pivot = partition(first, last);
quickSort(first, pivot);
quickSort(pivot + 1, last);
}
}
int main(int argc, char** argv)
{
string algorithm = "selection";
string dataset = "random";
for (int c; (c = getopt(argc, argv, "ravqsin")) != -1;) {
switch (c) {
case 'r':
dataset = "random";
break;
case 'a':
dataset = "sorted";
break;
case 'v':
dataset = "reverse";
break;
case 'q':
algorithm = "quicksort";
break;
case 's':
algorithm = "selection";
break;
case 'i':
algorithm = "insertion";
break;
case 'n':
algorithm = "none";
break;
}
}
argc -= optind;
argv += optind;
const int size = argc > 0 ? atoi(argv[0]) : 10000;
int* data = new int[size];
if (dataset == "sorted") {
for (int i = 0; i < size; ++i) {
data[i] = i;
}
}
else if (dataset == "reverse") {
for (int i = 0; i < size; ++i) {
data[i] = size - i - 1;
}
}
else if (dataset == "random") {
for (int i = 0; i < size; ++i) {
data[i] = rand() % size;
}
}
if (algorithm == "quicksort") {
quickSort(data, data + size);
}
else if (algorithm == "selection") {
selectionSort(data, data + size);
}
else if (algorithm == "insertion") {
insertionSort(data, data + size);
}
else if (algorithm=="none"){
cout<< "Oops!" <<'n';
exit(1);
}
cout << "OK" << 'n';
cout << "Algorithm:   " << algorithm << 'n';
cout << "Data set:    " << dataset << 'n';
cout << "Size:        " << size << 'n';
cout << "Swaps:       " << swaps << 'n';
cout << "Comparisons: " << comparisons << 'n';
return 0;
}

Answer 1

在quickSort函数中，更改

if ((first - last) <= 1)

自

if ((last - first) <= 1)