Comparison and Swaps Counter for Quicksort only Outputting 0 no matter the data size or list sorting

[iampenguintm]

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.

using namespace std;
unsigned long long comparisons = 0;
unsigned long long swaps = 0;

bool comp_less(int a, int b){
    ++comparisons;

    if ( comparisons == 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 == 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;
}

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);
    }
}

[salem c]

1. It's not worth deleting the few lines you omitted that prevent everyone else from doing simple copy/paste/compile/test runs.

#include <iostream>
#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 == 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 == 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;
}

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 a[] = { 1, 4, 6, 1, 3, 4, 8, 22 };
  quickSort(a,a+8);
  cout << a[4] << endl;
  cout << comparisons << endl;
  cout << swaps << endl;
}

They print 0, because your code never executes.

$ g++ -g bar.cpp
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) b main
Breakpoint 1 at 0x400b54: file bar.cpp, line 70.
(gdb) run
Starting program: /home/sc/Documents/a.out 

Breakpoint 1, main () at bar.cpp:70
70	int main( ) {
(gdb) n
71	  int a[] = { 1, 4, 6, 1, 3, 4, 8, 22 };
(gdb) 
72	  quickSort(a,a+8);
(gdb) s
quickSort (first=0x7fffffffde30, last=0x7fffffffde50) at bar.cpp:61
61	        if ((first - last) <= 1)
(gdb) 
62	            return;
(gdb) 
68	}
(gdb) 
main () at bar.cpp:73
73	  cout << a[4] << endl;

It just returns immediately, having done nothing at all.

[keskiverto]

Indeed. In the example:
first = a
last = a + 8
(first - last) = a - (a + 8) = -8


Note you reset swaps:

    if ( comparisons == numeric_limits<unsigned long long>::max() )
    {
        std::cout << "Number of comparisons reached max value. Resetting it 0.\n";
        swaps = 0;
    }

How much is numeric_limits<unsigned long long>::max() + 1 anyway?
How much is comparisons %= numeric_limits<unsigned long long>::max()?