#include <iostream>
using namespace std;
// A function implementing Shell sort.
void ShellSort(int a[], int n)
{
int i, j, k, temp;
// Gap 'i' between index of the element to be compared, initially n/2.
for(i = n/2; i > 0; i = i/2)
{
for(j = i; j < n; j++)
{
for(k = j-i; k >= 0; k = k-i)
{
// If value at higher index is greater, then break the loop.
if(a[k+i] >= a[k])
break;
// Switch the values otherwise.
else
{
temp = a[k];
a[k] = a[k+i];
a[k+i] = temp;
}
}
}
}
}
int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
ShellSort(arr, n);
// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gQSBmdW5jdGlvbiBpbXBsZW1lbnRpbmcgU2hlbGwgc29ydC4Kdm9pZCBTaGVsbFNvcnQoaW50IGFbXSwgaW50IG4pCnsKCWludCBpLCBqLCBrLCB0ZW1wOwoJLy8gR2FwICdpJyBiZXR3ZWVuIGluZGV4IG9mIHRoZSBlbGVtZW50IHRvIGJlIGNvbXBhcmVkLCBpbml0aWFsbHkgbi8yLgoJZm9yKGkgPSBuLzI7IGkgPiAwOyBpID0gaS8yKQoJewoJCWZvcihqID0gaTsgaiA8IG47IGorKykKCQl7CgkJCWZvcihrID0gai1pOyBrID49IDA7IGsgPSBrLWkpCgkJCXsKCQkJCS8vIElmIHZhbHVlIGF0IGhpZ2hlciBpbmRleCBpcyBncmVhdGVyLCB0aGVuIGJyZWFrIHRoZSBsb29wLgoJCQkJaWYoYVtrK2ldID49IGFba10pCgkJCQlicmVhazsKCQkJCS8vIFN3aXRjaCB0aGUgdmFsdWVzIG90aGVyd2lzZS4KCQkJCWVsc2UKCQkJCXsKCQkJCQl0ZW1wID0gYVtrXTsKCQkJCQlhW2tdID0gYVtrK2ldOwoJCQkJCWFbaytpXSA9IHRlbXA7CgkJCQl9CgkJCX0KCQl9Cgl9Cn0KaW50IG1haW4oKQp7CQoJaW50IG4sIGk7Cgljb3V0PDwiXG5FbnRlciB0aGUgbnVtYmVyIG9mIGRhdGEgZWxlbWVudCB0byBiZSBzb3J0ZWQ6ICI7CgljaW4+Pm47CiAKCWludCBhcnJbbl07Cglmb3IoaSA9IDA7IGkgPCBuOyBpKyspCgl7CgkJY291dDw8IkVudGVyIGVsZW1lbnQgIjw8aSsxPDwiOiAiOwoJCWNpbj4+YXJyW2ldOwoJfQogCglTaGVsbFNvcnQoYXJyLCBuKTsKIAoJLy8gUHJpbnRpbmcgdGhlIHNvcnRlZCBkYXRhLgoJY291dDw8IlxuU29ydGVkIERhdGEgIjsKCWZvciAoaSA9IDA7IGkgPCBuOyBpKyspCgkJY291dDw8Ii0+Ijw8YXJyW2ldOwogCglyZXR1cm4gMDsKfQ==