Shell Sort replaces element of array with -858993460

Question

Okay, so I am currently writing a shell sort function for a Data Structures and Algorithms I am currently taken. We were given the algorithm itself, but asked to write it for a templated type in C++. After writing what I thought was right, the sort bugs out after 7 iterations, and replaces the highest number in my sort with -858993460.

template <class T>
void shellSort(T list [], int size)
{
    int gap = size / 2;
    while (gap > 0)
    {
        for (size_t i = 0; i < size - gap; i++)
        {
            if (list[i] > list[i + gap])
            {
                swap(list, list[i], list[i + gap]);
            }
            for (int j = 0; j < size; j++)
            {
                cout << list[j] << " ";
            }
            cout << endl;
        }
        gap /= 2;

    }

    bubbleSort(list, size);

}

before I run the Shell Sort I reset the values of the Array to a random assortment just to test the other sorts, using

void resetArray(int list [])
{
    list[0] = 5;
    list[1] = 2;
    list[2] = 7;
    list[3] = 2;
    list[4] = 3;
    list[5] = 4;
    list[6] = 1;

    cout << "List Reset. List is Now: ";
    for (size_t i = 0; i < 6; i++)
    {
        cout << list[i] << " ";

    }
    cout << endl;
}

and the output by my sort goes

5 2 4 2 3 7 1
5 2 4 2 3 7 1
5 2 4 2 3 7 1
5 4 2 2 3 7 1
5 4 2 2 7 3 1
5 4 -858993460 2 2 3 1
5 4 -858993460 2 2 3 1

`-858993460`, when displayed has hex, is 0xcccccccc. See http://en.wikipedia.org/wiki/Magic_number_%28programming%29 — Keith Thompson, Sep 26 '13 at 22:50
You're missing the `swap` function. The problem is likely _there_ (or in `bubbleSort`, which is also missing): http://ideone.com/JOxcSM — sehe, Sep 26 '13 at 22:52
[When and why will an OS initialise memory to 0xCD, 0xDD, etc. on malloc/free/new/delete?](https://stackoverflow.com/q/370195/995714) — phuclv, Aug 18 '18 at 11:13

score 3 · Accepted Answer · answered Sep 26 '13 at 22:50

3

Without seeing your swap, I say that the culprit is this line:

swap(list, list[i], list[i + gap]);

You are passing the values in positions 2 and 3, where indexes are almost certainly expected. This call should look like this:

swap(list, i, i + gap);

Otherwise, the swap would interpret the values of the array as indexes to be swapped, reading memory outside the array.

To avoid problems like this in the future, use std::swap instead:

std::swap(list[i], list[i + gap]);

answered Sep 26 '13 at 22:50

Sergey Kalinichenko

714,442
84
1,110
1,523

1

How do you know what his `swap` function looks like? I don't recognize this as anything standard. – sehe Sep 26 '13 at 22:50
@sehe I don't know for sure, but since it takes thee parameters, and because `list` is one of them, the remaining two are bound to be indexes :-) – Sergey Kalinichenko Sep 26 '13 at 22:52
2

@sehe: There's no reason for a `swap` function to take three arguments unless they're an array and two indices. If the items to be swapped are passed by reference, only those items are needed. – Keith Thompson Sep 26 '13 at 22:52
@dasblinkenlight Really? I wouldn't be so confident at this level of coding (that also takes an `array` by decayed pointer, calls that array `list` and uses signed/unsigned comparisons) – sehe Sep 26 '13 at 22:53
The output shows it works for some inputs. then we must see the code first. – masoud Sep 26 '13 at 22:53
@KeithThompson Well. Derp. I know, right. See my comment at the OP – sehe Sep 26 '13 at 22:54
@MM. That's because all his data except `7` at index `2` are valid indexes into the array of six items. – Sergey Kalinichenko Sep 26 '13 at 22:55
1

@dasblinkenlight: Ummm, yes. Nice wild guess. +1 – masoud Sep 26 '13 at 22:56
1

Yeah, that one line was the problem my swap is just a basic tmp = list[first]; list[first] = list[second]; and list[second] = tmp; thanks for the help – Fluzzarn Sep 26 '13 at 22:59

Shell Sort replaces element of array with -858993460

1 Answers1