Incorrect Comparisons And Swaps Counter Output for Quicksort Function

Question

Im currently trying to implement a c++ program which compares the number of swaps and comparisons in a variety of different sorting methods. The program appears to be working perfectly for all sorting methods (selection sort, insertion sort) except quicksort which only outputs a comparison and swap count of 0 no matter the data size or order of the list. Ive included the full program below. The quicksort function is definitely working its only the counting element which isn't which is strange since it uses external compare and swap functions which are meant to increment the appropriate counter each time they are called. Any help is greatly appreciated.

#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

In your quickSort function, change

if ((first - last) <= 1)

to

if ((last - first) <= 1)