Data Structure: How to implement Shell Sort in C++?

Shell is generalization of insertion sort and is devised by Donald Shell in 1954. The method sorts separate sub-files of original file i.e.

Divide the original file into smaller sub-files.
Sort individual sub-files using any sorting algorithm

We choose increment ‘k’ for dividing the original file into smaller sub-files and process is repeated until k becomes 1.

Source Code:

#include<iostream>
using namespace std;
class ShellSort{
    private:
        int no_of_elements;
        int elements[10];
    public:
        void getarray();
        void sortit(int [], int);
        int return_noelements();
        void display();
};
void ShellSort::getarray(){
    cout<<"How many elements? ";
    cin>>no_of_elements;
    cout<<"Insert array of element to sort: ";
    for(int i=0;i<no_of_elements;i++){
        cin>>elements[i];
    }
}
int ShellSort::return_noelements(){
    return no_of_elements;
}
void ShellSort::sortit(int incrmnts[], int numinc){
    int incr, j, k, span, y;
    for(incr = 0; incr < numinc; incr++){
        span = incrmnts[incr];
        for(j = span; j < no_of_elements; j++){
            y = elements[j];
            for(k = j - span; k >=0 && y < elements[k]; k-=span){
                elements[k+span] = elements[k];
            }
            elements[k+span] = y;
        }
        cout<<"Iteration = "<<incr+1<<" Span = "<<span<<" : ";
        display();
        if (span==1)
        break;
    }
}
void ShellSort::display(){
    for(int i = 0 ; i < no_of_elements; i++){
        cout<<elements[i]<<" ";
    }
    cout<<endl;
}
int main(){
    ShellSort SHS;
    int n, i, j;
    SHS.getarray();
    n = SHS.return_noelements();
    int incrmnts[n];
    for(i = n,j = 0; i > 0; i = i/2, j++){
        incrmnts[j] = i;
    }
    SHS.sortit(incrmnts, j+1);
    return 0;
}

Output:

How many elements? 7
Insert array of element to sort: 75 12 36 35 25 99 62
Iteration : 1 Span = 7 : 75 12 36 35 25 99 62
Iteration : 2 Span = 3 : 35 12 36 62 25 99 75
Iteration : 3 Span = 1 : 12 25 35 36 62 75 99

دراسات تقنية

Data Structure: How to implement Shell Sort in C++?

إرسال تعليق

Data Structure: How to implement Shell Sort in C++?

آخر المشاركات

تعليقات: 0

إرسال تعليق