0

I have an assignment where I have to create a function that counts the number of swaps and comparisons done by a shell sort. However, the numbers that the function returns for each is pretty big. I am using structs to hold the values for the swaps and comparisons, but I think I'm putting them in a weird spot. 

struct SwapAndComp {
    long long swaps;
    long long comps;
};

SwapAndComp insertionSortInterleaved(long numbers[], long numbersSize, long startIndex, long gap, long long& swaps, long long& comps) {
    SwapAndComp shell;
    int i = 0;
    int j = 0;
    int temp = 0;  

    for (i = startIndex + gap; i < numbersSize; i = i + gap) {
        j = i;
        while (j - gap >= startIndex) {
            comps++;
            if (numbers[j] < numbers[j - 1]) {
                temp = numbers[j];
                numbers[j] = numbers[j - gap];
                numbers[j - gap] = temp;
                j = j - gap;
                swaps++;
            }
            else break;
        }
    }

    shell.swaps = swaps;
    shell.comps = comps;
    return shell;
}
SwapAndComp shellSort(long numbers[], long numbersSize, long gapArray[], long numGaps, long long& swaps, long long& comps) {
    SwapAndComp once;
    SwapAndComp total;
    for (int i = 0; i < numGaps; i++) {
        for (int j = 0; j < gapArray[i]; j++) {
            once = insertionSortInterleaved(numbers, numbersSize, j, gapArray[i], total.swaps, total.comps);
            total.swaps += once.swaps;
            total.comps += once.comps;
        }
    }
    return total;
}

I think the problem is in the shell sort function. I'm trying to add all of the swaps and comparisons from each of the insertionSortInterleaved function, but when I call it in the main with an array size of 5000, I get

Shell Sort: Time: 0.01 Swaps: -3814709954702659342 Comps: -2522982850760493548

As you can see, I get a big negative number. I'm not sure if it's because the loops go out of bounds or what, but it is confusing me a bit. Any help would be appreciated! Thanks!

quickfire2
  • 1
  • 1
  • So... what is the initial value of `total.swaps`? – KamilCuk Mar 13 '20 at 21:30
  • With what values do you initialize swaps and comps? – Tarek Dakhran Mar 13 '20 at 21:30
  • Does this answer your question? [What happens to a declared, uninitialized variable in C? Does it have a value?](https://stackoverflow.com/questions/1597405/what-happens-to-a-declared-uninitialized-variable-in-c-does-it-have-a-value) – Tarek Dakhran Mar 13 '20 at 21:32
  • I was just thinking about that as I was walking out the door. It's weird though because I have it uninitialized in the struct but it still works when I use them for my selection sort and normal insertion sort functions. – quickfire2 Mar 13 '20 at 21:52

0 Answers0