I've been struggling with an issue in my Shell sort implementation for several days now. Specifically, I'm using gaps of 5, 3, and 1 for successive passes, but I'm encountering problems where elements that should be swapped are not being swapped. Here's an example:
Input Description:
Output Description:
Solution:
template<class type>
void shell_sort(vector<type>& a, int b[], int t)
{
//vector a: Contains elements to be sorted.
//array b: Stores the gaps for each pass of Shell sort.
//t: Number of passes to execute.
int length = a.size();
for (int index = 0; index < t; index++)
{
int gap = b[index];
cout << gap << endl;
for (int i = gap; i < length; i++)
{
type temp = a[i];
int j = i;
cout << "a[j] and a[j-gap]: " << a[j] << " " << a[j - gap] << endl;
while (j >= gap && a[j - gap] > temp)
{
cout << "a[j] and a[j-gap] swapped: " << a[j] << " " << a[j - gap] << endl;
a[j] = a[j - gap];
j -= gap;
}
a[j] = temp;
}
print_vector(a);
cout << endl;
}
}
Example Input:
0
49 38 65 97 76 13 27 49 55 4
3
5 3 1
Expected Output:
5
13,27,49,55,4,49,38,65,97,76
3
13,4,49,38,27,49,55,65,97,76
1
4,13,27,38,49,49,55,65,76,97
My output with debug statements:
0
49 38 65 97 76 13 27 49 55 4
3
5
a[j] and a[j-gap]: 13 49
a[j] and a[j-gap] swapped: 13 49
a[j] and a[j-gap]: 27 38
a[j] and a[j-gap] swapped: 27 38
a[j] and a[j-gap]: 49 65
a[j] and a[j-gap] swapped: 49 65
a[j] and a[j-gap]: 55 97
a[j] and a[j-gap] swapped: 55 97
a[j] and a[j-gap]: 4 76
a[j] and a[j-gap] swapped: 4 76
13,27,49,55,4,49,38,65,97,76
3
a[j] and a[j-gap]: 55 13
a[j] and a[j-gap]: 4 27 //4 and 27 should be swapped but didnt
a[j] and a[j-gap]: 49 49
a[j] and a[j-gap]: 38 55
a[j] and a[j-gap] swapped: 38 55
a[j] and a[j-gap]: 65 4
a[j] and a[j-gap]: 97 49
a[j] and a[j-gap]: 76 55
13,27,49,38,4,49,55,65,97,76
1
a[j] and a[j-gap]: 27 13
a[j] and a[j-gap]: 49 27
a[j] and a[j-gap]: 38 49
a[j] and a[j-gap] swapped: 38 49
a[j] and a[j-gap]: 4 49
a[j] and a[j-gap] swapped: 4 49
a[j] and a[j-gap]: 49 49
a[j] and a[j-gap]: 55 49
a[j] and a[j-gap]: 65 55
a[j] and a[j-gap]: 97 65
a[j] and a[j-gap] swapped: 76 97
13,27,38,4,49,49,55,65,76,97
The issue is that even though my debug statements show the correct comparisons, some elements are not swapped as expected during the sorting process. I've tried using swap() but the result remains the same, seems like it's not a swapping method problem. I'm unsure where the problem lies in my code. Any insights or suggestions would be greatly appreciated. Thank you!
Appendix: complete code
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;
template<class type>
void print_vector(vector<type>& v)
{
//cout << "printing result" << endl;
for (auto i = v.begin(); i != v.end(); ++i) {
cout << *i;
if (i != v.end() - 1) { cout << ","; }
}
}
template<class type>
void shell_sort(vector<type>& a, int b[], int t)
{
int length = a.size();
for (int index = 0; index < t; index++)
{
int gap = b[index];
cout << gap << endl;
for (int i = gap; i < length; i++)
{
type temp = a[i];
int j = i;
cout << "a[j] and a[j-gap]: " << a[j] << " " << a[j - gap] << endl;
while (j >= gap && a[j - gap] > temp)
{
cout << "a[j] and a[j-gap] swapped: " << a[j] << " " << a[j - gap] << endl;
a[j] = a[j - gap];
j -= gap;
}
a[j] = temp;
}
print_vector(a);
cout << endl;
}
}
template<class type>
void solution()
{
//cout << "in solution"<<endl;
string to_sort;
getline(cin, to_sort);
vector<string> sort_v;
stringstream ss(to_sort);
string word;
while (ss >> word) {
sort_v.push_back(word);
}
//print_vector(sort_v);
//cout << endl;
int t;
cin >> t;
int* b = new int[t];
for (int i = 0; i < t; i++)
{
cin >> b[i];
}
shell_sort(sort_v, b, t);
}
int main()
{
int flag;
cin >> flag;
cin.ignore();
if (flag == 0)
{
solution<int>();
}
else if (flag == 1)
{
solution<double>();
}
else if (flag == 2)
{
solution<char>();
}
else if (flag == 3)
{
solution<string>();
}
else
{
cout << "err" << endl;
}
return 0;
}
The problem is in your solution function.
In the example you provided this template function is specialised with type being int (as flag is 0), but the code in solution still stores the values in a vector<string>, ignoring that type. And so the shell_sort template is specialised with string type and not int.
In short, you are sorting strings, not integers. You need to convert strings to integers.