C++ program for Shell Sort
Description
Shell sort is a highly efficient sorting algorithm and is based on insertion sort algorithm.
This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left.
shell sort is a "diminishing Incremental Sort". better known as a "comb Sort"
This algorithm uses insertion sort on a widely spread elements, first to sort them and then sorts the less widely spaced elements.
Or it an be said this algorithm takes multiple passes through the list and each time sorts a number of equally sized sets using the insertion sort.
The size of the set to be sorted get larger with each pass through the the list, until the set consist of entire list .
The item contained in each set are not contiguous rather. If there are i sets that a set is composed of every ith element.
C++ program for Shell Sort
using namespace std;
// Shell sort
void shellSort(int a[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int i = n / 2; i > 0; i /= 2) {
for (int j = i; j < n; j += 1) {
int temp = a[j];
int k;
for (k = j; k >= i && a[k - i] > temp; k -= i) {
a[k] = a[k - i];
}
a[k] = temp;
}
}
}
// Driver code
int main() {
int n,i;
cout<<"Enter No. of elements\n";
cin>>n;
int a[n];
cout<<"Enter elements of array\n";
for(i=0 ; i<n ; i++)
{
cin>>a[i];
}
int size = sizeof(a) / sizeof(a[0]);
shellSort(a, size);
cout << "Sorted array: \n";
for (i = 0; i < size; i++){
cout << a[i] << " ";
}
cout << endl;
return 0;
}
Output
Enter no. of elements
5
Enter elements of array
54
87
12
45
76
Sorted Array:
12 45 54 76 87
Comments