Shell Sort Algorithm with C++ Code | Sorting Algorithms | Data Structures & Algorithms

ShellSort is an in-place comparison sort.  It is mainly a variation of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left. The idea of shell sort is to allow exchange of far items. This spacing is termed as interval or gap. ShellSort is more efficient compared to Insertion Sort or Bubble sort specially when –

  • 1. Smaller value elements are towards the end of the array/list
  • 2. Large sized array/list
  • 3. Efficiency depends on how we select the GAP/interval

Time Complexity –

  • 1. Best Case – Ω(n log(n))
  • 2. Worst Case – O(n^2)
  • 3. Average Case – θ(n log(n)2)

Space Complexity – O(1)

Working –
  • Step 1 − Initialize the value of gap/interval (here we take n/2 iteratively)
  • Step 2 − Compare 2 elements at the distance of gap at every iteration
  • Step 3 − if element at the left is smaller than element at the right, perform swap or shift(depending on whether you use bubble sort or insertion sort respectively)
  • Step 3 − Repeat until complete list is sorted.
C++ Program to Implement Shell Sort –
// C++ implementation of Shell Sort 
#include<iostream> 
using namespace std; 
void ShellSort(int arr[], int n)
{
	for(int gap=n/2;gap>0;gap /= 2)
	{
		for(int j = gap;j<n;j+=1)
		{
			int temp = arr[j];
			int i=0;
			
			for(i=j;(i>=gap)&&(arr[i-gap]>temp);i-=gap)
			{
				arr[i] = arr[i-gap];
			}
			arr[i] = temp;
		}
	}
}

int main() 
{ 
	int n;
	cout<<"Enter the size of the array: "<<endl;
	cin>>n;
	int arr1[n],arr2[n];
	
	cout<<"Enter "<<n<<" integers in any order"<<endl;
	for(int i=0;i<n;i++)
	{
		cin>>arr1[i];
		arr2[i]=arr1[i];
	}
	
	cout<<endl<<"Before Sorting: "<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<arr1[i]<<" ";
	}
		
	cout<<endl<<endl<<"SHELL SORT "<<endl;
	
	ShellSort(arr1, n); // SHELL SORT CALLED HERE
   
	cout<<endl<<"After Sorting: "<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<arr1[i]<<" ";
	}
	
   return 0; 
}
YouTube video tutorial –

Leave a Reply

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