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