# Shell Sort

Shell Sort is a sorting technique. It is an sorting technique that repeatedly uses insertion sort method to sort the sub-lists that are created by defining the step. It’s a simple and efficient algorithm with complexity of O(n) to O(n^2).

The basic mechanism of Shell Sort is –

Avoid the farther movement of a data element by inserting it at its correct sorted position. To do this the whole array is divided into sub-lists that are spread across the array such that the number of movements of elements with insertion sort is minimized in each subsequent passes. With every pass the number sub-lists are redefined by reducing partitions.

If you have medium count of array elements to be sorted this efficient works the best. It’s not very efficient for large data sets.

#### Basic Steps of Shell Sort

1. Define the interval for creating scattered sub-lists throughout the array.
2. Repeat steps 2 and 3 while all elements are not accessed.
3. Call Insertion Sort for the sub-lists of elements using the interval (partition) defined step 1.
4. Redefine the interval

The interval is calculated by Knuth’s formula defined as

Interval = interval * 3 + 1 where interval is initialized with value 1

The repeated use of Insertion sort on interval based sub-lists limits the movement of far places. As element’s movement within sub-list, the size of sub-lists keep on increasing as the interval size reduces.

#### Shell Sort –C

```#include <stdio.h>
#include<conio.h>
int data;
int num;
void inssort(int );
void display(int );
void main()
{
int ind, h=1;
//Ask for the number of elements of dataset
printf("Size of Data Set:");
scanf("%d",&num);
//Enter unsorted elements of data set
printf("Enter elements:\n");
for (ind=1;ind<=num;ind++)
{
scanf("%d",&data[ind]);
}
//Initialize the first interval size
while (h<num/3)
h=h*3+1;

while (h>0)
{
inssort(h);
display(h);
//redfine the interval size
if (num%2==0)
h=h/3;
else
h=(h-1)/3;
}
getch();
}
// insertion sort for the sub lists defined with current interval
void inssort(int h)
{
int i,j,k,temp;
for (k=h;k<=num;k++)
{
//store the element to be inserted
temp=data[k];
j=k;
while((j>h-1) && (data[j-h]>=temp))
{
//interchange elements
data[j]=data[j-h];
j=j-h;
}
data[j]=temp;
}
}
// diaplay the elemnts of the data set
void display(int h)
{
int ind;
printf("\nState of Elements after interval size =%d are:\n",h);
for (ind=1;ind<=num;ind++)
{
printf("%d \t",data[ind]);
}
}```

#### Shell Sort –Java

```import java.io.*;
class shellsort
{
void begin(int data[])
{
int ind, h=0;
int num;
num=data.length;
//Initialize the first interval size
while (h<num/3)
h=h*3+1;

while (h>0)
{
inssort(data,num,h);
display(data,num,h);
//redfine the interval size
if (num%2==0)
h=h/3;
else
h=(h-1)/3;
}
}
// insertion sort for the sub lists defined with current interval
void inssort(int data[], int num, int h)
{
int i,j,k,temp;
for (k=h;k<num;k++)
{
//store the element to be inserted
temp=data[k];
j=k;
while((j>h-1) && (data[j-h]>=temp))
{
//interchange elements
data[j]=data[j-h];
j=j-h;
}
data[j]=temp;
}
}
//Display the elements
void display(int data[], int num, int h)
{
int ind;
System.out.println("\nState of Elements after interval size are:"+h);
for (ind=0;ind<num;ind++)
{
System.out.println(data[ind]+"\t");
}
}

public static void main(String args[])
{
//Declare and initialize data array
int data[]  = {7,8,2,1,9,22,6,72,91,23};
//create Shellsort object using constructor
shellsort ss= new shellsort();
//Call Shell Sort method
ss.begin(data) ;
}
}```

#### Shell Sort – Python

```data=[];
num=0;

#insertion sort for the sub lists defined with current interval
def inssort(h):
i=0
j=0
k=0
temp=0
k=h
while (k<num):
temp=data[k]
j=k
while((j>h-1) and (data[j-h]>=temp)):
data[j]=data[j-h]
j=j-h
data[j]=temp
k=k+1

#display the elemnts of the data set
def display(h):
ind=0
print("\nState of Elements after interval size =",h," are:\n")
while (ind <num):
print(data[ind])
ind=ind+1

ind=0
h=1
#Ask for the number of elements of dataset
num=(int)(input("Input size of dataset--->"))
#Enter unsorted elements of data set
print("Enter elements:")
while (ind < num):
data.append((int)(input("input value--->")))
ind=ind+1
#Initialize the first interval size
while h<(int)(num/3):
h=h*3+1

while h>0:
inssort(h)
display(h)
#redfine the interval size
if (num%2==0):
h=(int)(h/3)
else:
h=(int)((h-1)/3	)
```