Home »
C++ programming language
Implement shell sort using C++ program
In this article, we are going to learn what is shell short in Data Structure and how to implement it using a C++ program?
Submitted by Shubham Singh Rajawat, on July 24, 2017
Shell sort is a generalization of insertion sort in which the exchange of far element is possible unlike insertion sort with the help of an element ‘gap’ and make the list gap-sorted we will keep decreasing gap until gap becomes 1 which means the last step will be a normal insertion sort.
Algorithm:
Step 1: Initialize the value of gap.
Step 2: Divide the list into smaller sub-lists of equal interval gap.
Step 3: Sort each sub-list using insertion sort.
Step 4: Repeat until the list is sorted.
Consider the given program:
#include<iostream>
using namespace std;
/*Method to sort the list/array*/
void shellSort(int sort[],int size)
{
for(int gap=size/2;gap>0;gap/=2)
{
for(int i=gap;i<size;i++)
{
int temp=sort[i];
int j;
for(j=i; j>=gap && sort[j-gap]>temp; j-=gap)
{
sort[j]=sort[j-gap];
}
sort[j]=temp;
}
}
}
//main program
int main()
{
int size;
cout<<"Enter the size of the array :";
cin>>size;
int sort[size];
for(int i=0;i<size;i++)
{
cin>>sort[i];
}
shellSort(sort,size);
cout<<"Array after sorting is :";
for(int i=0;i<size;i++)
{
cout<<sort[i]<<" ";
}
cout<<endl;
return 0;
}
Output
FIRST INPUT:
Enter the size of the array :6
87 15 34 99 56 44
Array after sorting is :15 34 44 56 87 99
SECOND INPUT :
Enter the size of the array :10
13 54 36 87 36 42 11 68 91 9
Array after sorting is :9 11 13 36 36 42 54 68 87 91