Shell Sort Implementation in C++

How to implement Shell Sort in C++?

It is an in-place comparison sort and one of the oldest sorting algorithm.
Shell sort is a generalization of insertion sort that allows the exchange of items that are far apart. It is not stable sort. It takes O(1) extra space. The worst case time complexity of shell sort depends on the increment sequence.

How it works :

1. Compare elements that are far apart.
2. Compare elements that are less far apart. Narrower array.
3. Do this repeatedly, reach to a point where compare adjacent elements.
4. Now the elements will be sufficiently sorted that the running time of the final stage will be closer to O(N).

It is also called diminishing increment sort.

You make like

Selection Sort in C++

Heap Sort in C++

Insertion Sort in C++

Bubble Sort in C++

The following program has an input array of size 10 initialized with 10 values. This returns the array in non decreasing order using Shell Sort algorithm. This program is compiled with g++ compiler on a windows machine.

Please comment for any problem or help required.

Program to implement Shell Sort in C++:

#include <iostream>
using namespace std;

int main(void)
{
 int array[5]={4,5,2,3,6},i1=0;
 
 int i, j, increment, temp,number_of_elements=5;
 
 cout<<"\n Before Sorting:";
 for(i1=0;i1<5;i1++)
     cout<<"\n"<<array[i1];
 
 for(increment = number_of_elements/2;increment > 0; increment /= 2)
 {
     for(i = increment; i<number_of_elements; i++)
     {
         temp = array[i];
         for(j = i; j >= increment ;j-=increment)
         {
             if(temp < array[j-increment])
             {
                 array[j] = array[j-increment];
             }
             else
             {
                 break;
             }
         }
         array[j] = temp;
     }
 }
 cout<<"\n After Sorting:";
 
for(i1=0;i1<5;i1++)
 cout<<"\n"<<array[i1];
  
}

OUTPUT: