CODEWITHSUNDEEP
c++sorting
J. Doe
J. Doe

Reputation: 21

Swaps and comparisons in shell sort

I am trying to figure out how to find the total amount of swaps and comparisons used in a shell sort function, but I'm not really sure where to place the additions of swaps and comparisons.

I am putting the additions in this insertionSort function below.

void insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = startIndex + gap; i < numbersSize; i += gap) {
        j = i;
        while (j - gap >= startIndex && numbers[j] < numbers[j - 1]) {
            temp = numbers[j];
            numbers[j] = numbers[j - gap];
            numbers[j - gap] = temp;
            j = j - gap;
            totalComps++; //declared globally
            totalSwaps++; //declared globally
        }

    }
}

I know that the totalSwaps is fine where it is, but I'm not too sure where to put totalComps, since we're also comparing in the while loop.

Upvotes: 2

Views: 1534

Answers (3)

Caleth
Caleth

Reputation: 63039

You can use a pair of function objects, one that does the comparison and the other the swaps.

struct counted_less
{
    int count = 0;
    bool operator()(int lhs, int rhs)
    {
        ++count;
        return lhs < rhs;
    }
}

struct counted_swap
{
    int count = 0;
    void operator()(int & lhs, int & rhs)
    {
        ++count;
        using std::swap;
        swap(lhs, rhs);
    }
}


std::pair<int, int> insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    counted_less less;
    counted_swap swap;

    for (int i = startIndex + gap; i < numbersSize; i += gap) {
        for (int j = i; j - gap >= startIndex && less(numbers[j], numbers[j - 1]); j -= gap) {
            swap(numbers[j], numbers[j - gap]);
        }
    }

    return { less.count, swap.count };
}

Upvotes: 1

L. Scott Johnson
L. Scott Johnson

Reputation: 4402

Increment the conditional counter everytime you make a test.

A compact way to do so is to prefix the increment operation to every test with && (which will succeed since the count is positive, since the variable is pressumably unsigned):

for (i = startIndex + gap; ++totalComps && (i < numbersSize); i += gap) {

and

while (++totalComps && (j - gap >= startIndex) && ++totalComps && (numbers[j] < numbers[j - 1])) {

Upvotes: 0

SHR
SHR

Reputation: 8333

I think the compare should be count even if the condition was false

It meant only to array elements compares, not to each compare in your code...

see the following code

void insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = startIndex + gap; i < numbersSize; i += gap) {
        j = i;
        while (j - gap >= startIndex) {
            //each iteration is compare so increment here
            totalComps++; //declared globally
            if( numbers[j] < numbers[j - 1])  {
              temp = numbers[j];
              numbers[j] = numbers[j - gap];
              numbers[j - gap] = temp;
              j = j - gap;
              //had a swap
              totalSwaps++; //declared globally
            }
            else break;
        }

    }
}

Upvotes: 0

Related Questions