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[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 C code

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 Java

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	)
Python Code

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *