Shell Sort Algorithm in C, C++, Java with Examples | FACE Prep

In this article, we will be discussing about Shell Sort algorithm in C, C++, Java etc. Shell sort algorithm working, implementation, pseudo-code, time complexity, etc are also discussed here.

What is Shell Sort Algorithm?

Shell sort algorithm is very similar to that of the Insertion sort algorithm. In case of Insertion sort, we move elements one position ahead to insert an element at its correct position. Whereas here, Shell sort starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange.

A simple look at Shell Sort Vs Insertion Sort

insertion sort vs shell sort in c

Shelling out the Shell Sort Algorithm with Examples

Here is an example to help you understand the working of Shell sort on array of elements name A = {17, 3, 9, 1, 8}

shell sort algorithm in c

Shell Sort in C, C++, Java

Here is the implementation of Shell sort in C, C++ and Java.

#include<stdio.h>
int main()
{
int n, i, j, temp, gap;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for (gap = n/2; gap > 0; gap = gap / 2)
{

// Do a gapped insertion sort
// The first gap elements arr[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is gap sorted
for (i = gap; i < n; i = i + 1)
{

// add arr[i] to the elements that have been gap sorted
// save arr[i] in temp and make a empty space at index i
int temp = arr[i];

// shift earlier gap-sorted elements up until the correct location for arr[i] is found
for (j = i; j >= gap && arr[j - gap] > temp; j = j - gap)
arr[j] = arr[j - gap];

// put temp (the original arr[i]) in its correct position
arr[j] = temp;
}
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
#include<iostream>
using namespace std;
int main()
{
int n, i, j, temp, gap;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for (gap = n/2; gap > 0; gap = gap / 2)
{

// Do a gapped insertion sort
// The first gap elements arr[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is gap sorted
for (i = gap; i < n; i = i + 1)
{

// add arr[i] to the elements that have been gap sorted
// save arr[i] in temp and make a empty space at index i
int temp = arr[i];
// shift earlier gap-sorted elements up until the correct location for arr[i] is found
for (j = i; j >= gap && arr[j - gap] > temp; j = j - gap)
arr[j] = arr[j - gap];

// put temp (the original arr[i]) in its correct position
arr[j] = temp;
}
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
import java.util.Scanner;
public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i, j, temp, gap;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
for (gap = n/2; gap > 0; gap = gap / 2)
{

// Do a gapped insertion sort
// The first gap elements arr[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is gap sorted
for (i = gap; i < n; i = i + 1)
{
// add arr[i] to the elements that have been gap sorted
// save arr[i] in temp and make a empty space at index i
temp = arr[i];

// shift earlier gap-sorted elements up until the correct location for arr[i] is found
for (j = i; j >= gap && arr[j - gap] > temp; j = j - gap)
arr[j] = arr[j - gap];

// put temp (the original arr[i]) in its correct position
arr[j] = temp;
}
}
for(i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}

Shell Sort Time Complexity

Time complexity of above implementation of shellsort is O(n2). In the above implementation, gap is reduced by half in every iteration.