shell sort Algorithm

Shell sort, also known as Diminishing Increment Sort, is an efficient in-place comparison based sorting algorithm that is an extension of the insertion sort. It was invented by Donald L. Shell in 1959. The algorithm works by first arranging elements at a specific interval apart, forming a sub-array, and then sorting these sub-arrays using an insertion sort. After sorting the sub-arrays, the interval is reduced, and the process is repeated until the interval becomes one, making it a standard insertion sort. The advantage of shell sort over traditional insertion sort is that it can move elements to their correct positions much faster, as it takes advantage of the partially sorted sub-arrays. The performance of the shell sort algorithm largely depends on the choice of the interval sequence. The original shell sort algorithm used intervals of powers of two minus one, but further research has led to the discovery of more efficient interval sequences, such as the Pratt sequence, the Hibbard sequence, and the Sedgewick sequence. By choosing a good interval sequence, the shell sort algorithm can achieve a time complexity of O(n^(3/2)) or even O(n*log(n)), making it suitable for sorting medium-sized arrays. While it may not be as efficient as more advanced sorting algorithms like merge sort or quick sort, shell sort is relatively easy to implement and requires less overhead, making it a popular choice for certain applications.
//
// C++ implementation of shell sort
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/sorting
// https://github.com/allalgorithms/cpp
//
// Contributed by: Shradha Sharma
// Github: @shradha27
//
#include<iostream>
 
using namespace std;
 
// A function implementing Shell sort.
void ShellSort(int a[], int n)
{
	int i, j, k, temp;
	// Gap 'i' between index of the element to be compared, initially n/2.
	for(i = n/2; i > 0; i = i/2)
	{
		for(j = i; j < n; j++)
		{
			for(k = j-i; k >= 0; k = k-i)
			{
				// If value at higher index is greater, then break the loop.
				if(a[k+i] >= a[k])
				break;
				// Switch the values otherwise.
				else
				{
					temp = a[k];
					a[k] = a[k+i];
					a[k+i] = temp;
				}
			}
		}
	}
}
int main()
{	
	int n, i;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
 
	ShellSort(arr, n);
 
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
		cout<<"->"<<arr[i];
 
	return 0;
}

LANGUAGE:

DARK MODE: