In this post we’ll see how to write Shell sort program in Java.
Shell sort is based on another sorting algorithm insertion sort and it is developed by Donald L. Shell.
Shell sort – An improvement on insertion sort
In insertion sort the adjacent elements are compared and a swap is done if required (if item on the right is smaller than the item on the left). That way elements are shifted right to move smaller elements to the left.
Consider a scenario where a smaller element is on the far right, lot of shifting has to be done to move this element to its proper place on the left.
In shell sort rather than comparing adjacent elements, elements that are placed some distance from each other are compared and swapped. You start with a gap value and elements at that gap interval are compared. After each iteration gap value is decremented so that the interval is reduced, that is done until the gap value is 1 that is when adjacent elements are compared and shell sort effectively becomes insertion sort in that iteration.
The benefit is that by the last step, when the adjacent elements are compared, elements are almost sorted and no far off shifting of elements is required. For almost sorted elements insertion sort has the complexity of O(N) rather than O(N2).
Shell sort interval sequence calculation
The interval that is used for comparing elements is based on the number of elements. For the calculation of that interval Knuth’s interval sequence is used where the interval sequence is generated using the following formula-
gap = gap*3 + 1
When gap = 1 it gives interval value as 4, for gap =4 interval value as 13 and so on.
For example if you have an array of 20 elements the calculation for the initial interval value is done as follows in the Java program-
while(gap <= arr.length/3){
gap = (gap * 3) + 1;
}
For decrementing the interval following formula is used-
gap = (gap-1)/3
For example, When gap = 13 then the next interval sequence value will be (13-1)/3 = 4
Shell Sort Java program
public class ShellSort {
public static void main(String[] args) {
// Array of 20 elements
int[] intArr = {47, 85, 620, 3456, 7, 10, 4500, 106, 345,
1000, 67, 80, 5500, 34, 78, 782, 4, 0, 99, 190};
int[] sortedArray = shellSort(intArr);
System.out.println("Sorted array is- ");
for(int num : sortedArray){
System.out.print(num + " ");
}
}
private static int[] shellSort(int[] intArr){
int gap = 1;
int temp;
// initial gap value calculation
while(gap <= intArr.length/3){
gap = (gap * 3) + 1;
}
while(gap > 0){
for(int i = gap; i < intArr.length; i++){
temp = intArr[i];
int j;
for(j = i; j > gap - 1 && intArr[j-gap] >= temp; j=j-gap){
intArr[j] = intArr[j - gap];
}
intArr[j] = temp;
}
// next gap value calculation
gap = (gap - 1)/3;
}
return intArr;
}
}
Output
Sorted array is- 0 4 7 10 34 47 67 78 80 85 99 106 190 345 620 782 1000 3456 4500 5500
Shell Sort Explained
In the Java program for shell sort, since the array length is 20 so the initial gap value is calculated as 13. With that interval here are some values from the inner and outer loops.
In the first iteration value at index 13 is compared with index 0 and swapped too. Then the outer loop value is incremented by 1 (i = 14) at that time value at index 14 is compared with index 1 and swapped too. Same way iteration will happen until the length of the array is reached ( i = 19).
i -- 13 j-- 13 j-gap= 0 array after inner loop ---- 34 85 620 3456 7 10 4500 106 345 1000 67 80 5500 47 78 782 4 0 99 190 i -- 14 j-- 14 j-gap= 1 array after inner loop ---- 34 78 620 3456 7 10 4500 106 345 1000 67 80 5500 47 85 782 4 0 99 190 ... ... i -- 19 j-- 19 j-gap= 6
That’s the array after the iteration is done with gap value as 13.
34 78 620 4 0 10 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500
Then the gap value is reduced as per the formula and the new gap value is 4. With that again the comparison is done.
i -- 4 j-- 4 j-gap= 0 array after inner loop ---- 0 78 620 4 34 10 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500 i -- 5 j-- 5 j-gap= 1 array after inner loop ---- 0 10 620 4 34 78 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500 .. .. i -- 17 j-- 17 j-gap= 13 j-- 13 j-gap= 9 j-- 9 j-gap= 5 j-- 5 j-gap= 1 array after inner loop ---- 0 7 67 4 34 10 85 80 345 47 190 106 3456 78 620 782 5500 1000 99 4500 i -- 18 j-- 18 j-gap= 14 j-- 14 j-gap= 10 array after inner loop ---- 0 7 67 4 34 10 85 80 345 47 99 106 3456 78 190 782 5500 1000 620 4500 i – 19That’s the array after the iteration is done with gap value as 4.
0 7 67 4 34 10 85 80 345 47 99 106 3456 78 190 782 5500 1000 620 4500
Then the gap value is reduced again and it becomes 1. With value as 1 the sorting happens as in insertion sort giving the final sorted array.
Time and space complexity of shell sort
There are various estimates for the time complexity of shell sort based on the interval sequence used and the data used for sorting. But generally the time complexity of shell sort is considered O(N3/2) which means square root of (N)3.
Since shell sort is an in-place comparison sort so no extra space is required thus the space complexity of Shell sort is O(1).
That's all for this topic Shell Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
