Data Structure: How to implement Shell Sort in C++?

Shell is generalization of insertion sort and is devised by Donald Shell in 1954. The method sorts separate sub-files of original file i.e.

Divide the original file into smaller sub-files.

Sort individual sub-files using any sorting algorithm

We choose increment ‘k’ for dividing the original file into smaller sub-files and process is repeated until k becomes 1.

Source Code:

#include<iostream>
using namespace std;
class ShellSort

{
private:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit(int [], int);
int return_noelements();
void display();
};
void ShellSort::getarray(){
cout<<"How many elements? ";
cin>>no_of_elements;
cout<<"Insert array of element to sort: ";
for(int i=0;i<no_of_elements;i++){

cin>>elements[i];
}
}
int ShellSort::return_noelements(){
return no_of_elements;
}
void ShellSort::sortit(int incrmnts[], int numinc)

{
int incr, j, k, span, y;
for(incr = 0; incr < numinc; incr++)

{
span = incrmnts[incr];
for(j = span; j < no_of_elements; j++)

{
y = elements[j];
for(k = j - span; k >=0 && y < elements[k]; k-=span)

{
elements[k+span] = elements[k];
}
elements[k+span] = y;
}
cout<<"Iteration = "<<incr+1<<" Span = "<<span<<" : ";
display();
if (span==1)
break;
}
}
void ShellSort::display()

{
for(int i = 0 ; i < no_of_elements; i++)

{
cout<<elements[i]<<" ";
}
cout<<endl;
}
int main()

{
ShellSort SHS;
int n, i, j;
SHS.getarray();
n = SHS.return_noelements();
int incrmnts[n];
for(i = n,j = 0; i > 0; i = i/2, j++)

{
incrmnts[j] = i;
}
SHS.sortit(incrmnts, j+1);
return 0;
}

Output:

How many elements? 7
Insert array of element to sort: 75 12 36 35 25 99 62
Iteration : 1 Span = 7 : 75 12 36 35 25 99 62
Iteration : 2 Span = 3 : 35 12 36 62 25 99 75
Iteration : 3 Span = 1 : 12 25 35 36 62 75 99