Shell Sort
Shell sort, also known as Shell's method is an in-place comparison sort. It sorts the input either by exchange or sorting by insertion. It is mainly a variation of insertion sort. In insertion sort, we move elements only one position ahead. In this shell sort, it allows the exchange of far items. An array of n- elements is sorted if each of the sublists of every element is sorted.
Interval in Shell Sort:
The algorithm uses insertion sort on widely spread elements, first to sort them and then sorts less spread elements. This spacing is called an interval. The interval is calculated based on Knuth's formula as-
h = h * 3 + 1
Initially, the h value is set to 1.
Algorithm:
- Intitalize the value of interval using the formula
- Divide the array into smaller one of equal intervals
- Sort the sub-arrays using insertion sort
- The process is repeated until complete list is sorted
Example:
Let us, consider this above figure with the array of elements {5,3,2,0,4,9,7,1}. This is an unsorted array
so, the interval is calculated based on array length, which in this case is 8. Hence h will be an interval with a value of 4 which is calculated with the help of the below program.
int interval = 1;
while (interval < arr.length / 3) {
interval = interval * 3 + 1;
}
The element at the interval position of the array is compared with the array of i- th value subtracted from the interval. If the elements at these positions are not in sorted order they are swapped. This operation is performed till the interval is greater than zero. At every iteration, the interval is reduced using
interval = (interval - 1) / 3;
The following program performs shell sort on an array of elements.
public static void main(String[] args) {
int[] arr = { 4, 3, 2, 0, 1, 5, 7, 9 };
//Interval is set to 1 initially
int interval = 1;
while (interval < arr.length / 3) {
interval = interval * 3 + 1;
}
// This is the calculated interval value
// This loop runs till the interval is greater than zero.
while (interval > 0) {
for (int i = interval; i < arr.length; i++) {
//value holds the current i-th value int value = arr[i];
//inner holds the index value int inner = i;
while (inner > interval - 1 && arr[inner - interval] >= value) {
arr[inner] = arr[inner - interval];
inner = inner - interval;
}
//assigning the value to the array of the inner index.
arr[inner] = value;
}
//interval is reduced using below line
interval = (interval - 1) / 3;
}
//prints the sorte array
for (int i : arr) {
System.out.print(i + " ");
}
}
The time complexity of shell sort is O(n log n) for the best case and for all other cases it is based on the gap sequence.
The space complexity is O(1).
I hope you guys liked this article, here are some other articles you may like:
0 Comments