Sorting an Array Using Shell Sort Algorithm

Sorting an Array Using Shellsort

In this guide, we will sort the array using Shell’s algorithm – Shellsort. The algorithm works like this.

The array is divided into groups, each of which consists of two elements. The distance between pairs of elements is d=n/2, where n is the number of array elements. The elements of the pair are compared to each other and if needed, reversed. Then groups merge in pairs. Each new group has 4 elements, and distance between elements is d=d/2. Sorting is performed in the middle of the group, and then the groups are merged. The process continues as long as the distance between items becomes 1. At this point, the array is sorted by the method of insertion. The number of comparisons is 0.5*n3/2.

The solution in C++ looks like this:

#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
int v[20],                    
     n;                       
 int m_comp=0, m_move=0
void input() 
{
        cout<<"Enter number of elements (n<20)"<<endl; cin>>n;
        cout<<"Enter array"<<endl;
        for(int i=0;i<n;i++) cin>>v[i];
}
void output()
{
   for(int i=0;i<n;i++)                
     cout<<setw(5)<<v[i]<<" ";
   cout<<endl; } void sort() { for(int k=n/2;k>0;k/=2)              
     for(int i=k;i<n;i++) { m_comp++; for(int j=i-k;j>=0&&v[j]>v[j+k];j-=k)  
               {       int temp=v[j];          
                            v[j]=v[j+k];
                                       v[j+k]=temp;
                             m_move++;
                            output();         
                     }                        
}
}

void main() 
{ 
        cout<<"Sorting by Shell"<<endl;                                                                                                     
        input();
        cout<<"Array before sort"<<endl; output();
        sort();
        cout<<"Array after sort"<<endl; output();    
cout<<"m_comp="<<m_comp<<"  m_move="<<m_move<<endl; 
getch();
}

And the work of the program can be illustrated using this table:

Original array: a_input= {20,-5, 8, 7, 0, 3, -1, 4};

 

№ of iteration	Distance between the compared groups of elements	Groups of elements	Result of the iteration
i=1	d=n/2=8/2=4	{{20,-5, 8, 7} {0, 3,-1, 4}}	{{0,-5,-1, 4} {20,3,8, 7}}
i=2	d=d/2=4/2=2	{{0,-5} {-1,4} {20,3} {8,7}}{{-1,-5} {0,4} {20,3} {8,7}}{{-1, -5} {0, 3} {20,4} {8,7}}	{{-1,-5}{0,3}{8,4}{20,7}}
i=3	d=d/2=2/2=1	{{-1} {-5} {0} {3} {8} {4} {20} {7}}{{-5} {-1} {0} {3} {4} {8} {7} {20}}	{-5,-1, 0, 3, 4, 7, 8, 20}
End

 

In this guide, we have demonstrated how to sort an array using Shell sort algorithm – it should be read by students who have problems with similar topics. However, if you feel like you can’t handle your homework, feel free to leave it to Assignment.EssayShark.com. Our expert will complete your assignment according to your requirements and academic standards. The completed assignment will be concise and correspond the task that was set. Our experts can deal with a variety of different assignments for different disciplines. The expert will choose an individual technique to solve your particular problem.

The methods that our experts use depend on the discipline by which the work is done. Special recommendations and instructions provided by the student are strictly followed by our expert. Our expert can use practical, empirical, statistical, mathematical, diagnostic, and other methods to deal with your assignment. We are available 24/7 so you can contact us any time you want. You should not struggle on your own – leave your assignment to us and we will deal with it successfully.

 

Previous answers to this question

---

Get The Answer