Shellsort is an in-place comparison sort, also known as Shell sort or Shell’s method. It’s mainly variation of insertion sort or bubble sort . There was one drawback with insertion sort, we move elements only one position ahead but when an elements are too far then lots of movements are involved. To reduce these movements Shell sort come with idea of allow exchange of far items.

Shell Sort Steps

• Pick some far location h and make sorted array for values index[h…n-1] by insertion sort.
• Reduce the value of h until it becomes 1.
• Repeat the steps 1 and 2
• Finally you will get sorted items list.

Points to Remember

• Data structure: Array
• Worst-case performance: O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)
• Best-case performance: O(n log n) (most gap sequences) O(n log2n)  (best known worst case gap sequence)
• Average performance: depends on gap sequence
• Worst-case space complexity : О(n) total, O(1) auxiliary

Sell Sort Java Program

public class ShellSort {
public static void main(String[] args)
{
int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
System.out.println("Before Shell Sorting :");
printArray(items);

//Perform shell sort
shellsort(items);

System.out.println("After Shell Sorting :");
printArray(items);
}
static void shellsort(int items[])
{
int n = items.length;

// Start with a big gap, then reduce the gap until 1
for (int gap = n/2; gap > 0; gap /= 2)
{
//perform insertion sort for these gap size
//The first gap elements a[0..gap-1] are already
//in gapped order keep adding one more element
//until the entire array is gap sorted

for (int i = gap; i = gap && items[j - gap] > temp; j -= gap)
items[j] = items[j - gap];

// put temp in its correct  location
items[j] = temp;
}
}

}

static void printArray(int items[])
{
for (int item:items)
{
System.out.print(item + " ");
}
System.out.println();
}
}

Output

 

Before Shell Sorting :
2 6 3 8 4 1 5 0 
After Shell Sorting :
0 1 2 3 4 5 6 8