Shell Sort in C++

This C++ Program implements Shell Sort Algorithm.
Shell sort is a sorting algorithm. 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. Shell sort is not stable sort. It takes O(1) extra space. The worst case time complexity of shell sort depends on the increment sequence.

Shell sort steps are :
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 adjancent 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.

The program has an input array of size 10 initialized with 10 values. This returns the array in non decreasing order using Shell Sort algorithm.

Shell sort in C++

 

PROGRAM:

#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;
        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<<"After Sorting:";
    for(i1=0;i1<5;i1++)
    {cout<<array[i1];
    }

}

Leave a Reply