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
- Define the interval for creating scattered sub-lists throughout the array.
- Repeat steps 2 and 3 while all elements are not accessed.
- Call Insertion Sort for the sub-lists of elements using the interval (partition) defined step 1.
- 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[100];
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 )
Be First to Comment