c++ - 不正确的比较和交换计数器输出的Quicksort功能

Question

我目前正在尝试实现一个c++程序，该程序在各种不同的排序方法中比较交换次数和比较次数。该程序似乎对所有排序方法(选择排序，插入排序)都运行良好，除了quicksort之外，无论数据大小或列表的顺序如何，其仅输出比较和交换计数为0。 Ive在下面包括了完整的程序。 quicksort函数肯定只在使用它的计数元素，这并不奇怪，因为它使用了外部比较和交换函数，它们每次调用时都会增加适当的计数器。任何帮助是极大的赞赏。

#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)