Shell Sort
Shell Sort
Shell Sort is a variation of Insertion Sort. In this sort, we move the elements only one position forward.
Shellsort is the generalization of insertion sort, which overcomes the drawbacks of insertion sort by compared the elements separated by a gap of some positions.
This algorithm first sorts the elements are far away from each other, then it afterward reduces the gap between them. This gap is known as interval.
The interval is calculated by using the Knuth’s formula given below
-
- hh = h * 3 + 1
- where, ‘h’ is the interval having initial value 1.
Algorithm
ShellSort(a, n) for (interval = n/2; interval > 0; interval /= 2) for ( int i = interval; i < n; i += 1) temp = a[i]; for (j = i; j >= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort
Example of shellsort
Suppose the elements of array are
The original sequence of shellsort is N/2, N/4,….,1 as the intervals.
In the first loop, n is equal to 8 is size of the array, the elements are lying at the interval of 4 (n/2 = 4).If elements are not in oreder then elements will be compared and swapped.
In the first loop, the element at the zero position will be compared with the element at fourth position. If the zero element is greater then it will be swapped with element at 4th position. Otherwise, it remains the same position. This process will same and continue for the remaining elements.
At the interval of four, the sub lists are {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Now, the elements compare the values in every sub-list. After comparing the element, we have to swap this element, if required in the original array. After comparing and swapping the elements, the updated array look as follows –
In the 2nd loop, elements are lying at the interval of 2 (n/4 = 2), and n = 8.
Now, we are taking the interval of 2 to sort the array. With an interval of 2, two sublists will be crreated they are – {12, 25, 33, 40}, and {17, 8, 31, 42}.
Now, Again compare the values in every sublist. After comparing the element, we have to swap this element if required in the original array. After comparing and swapping the, the updated array look as follows –
In the 3rd loop, elements are lying at the interval of 1 (n/8 = 1), where n = 8. Lastly, we use the interval of value 1 to sort the the array of elements. In this step, shell sort using the insertion sort to sort the array elements.
This is array is sorted in ascending order.
Program of shellsort in C
#include <stdio.h>
// Shell sort
void shellSort(int array[], int n) {
// Rearrange elements
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print the array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
printf("Sorted array: \n");
printArray(data, size);
}
Output
Sorted array: 1 3 4 5 6 7 8 9
Program of shell sort in C++
#include <iostream>
using namespace std;
// Shell sort
void shellSort(int array[], int n) {
//arrange the elements
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print an array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
cout << "Sorted array: \n";
printArray(data, size);
}
Output
Sorted array: 1 3 4 5 6 7 8 9
Program of shellsort in Python
def shellSort(array, n):
#arrange the elements
interval = n // 2
while interval > 0:
for i in range(interval, n):
temp = array[i]
j = i
while j >= interval and array[j - interval] > temp:
array[j] = array[j - interval]
j -= interval
array[j] = temp
interval //= 2
data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Output
Sorted Array in Ascending Order: [1, 3, 4, 5, 6, 7, 8, 9]
Program of shell sort in Java
import java.util.Arrays;
// Shell sort
class ShellSort {
// Rearrange the elements
void shellSort(int array[], int n) {
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Driver code
public static void main(String args[]) {
int[] data = { 9, 8, 3, 7, 5, 6, 4, 1 };
int size = data.length;
ShellSort ss = new ShellSort();
ss.shellSort(data, size);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}
Output
Sorted Array in Ascending Order: [1, 3, 4, 5, 6, 7, 8, 9]
Shell sort complexity
The time complexity of Shellsort in the best case, average case, and worst case is as follows
1. Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n*logn) |
| Average Case | O(n*log(n)2) |
| Worst Case | O(n2) |
2. Space Complexity
| Space Complexity | O(1) |
| Stable | NO |
Shell Sort Applications
- Shellsort used to calling a stack is overhead.
uClibclibrary uses this sort. - Recursion exceeds a limit.
bzip2compressor uses it. - Insertion sort does not perform good when the close elements are far apart and Shell sort helps in reducing the distance between the close elements, therefore, there will be less no. of swappings to be performed.
Read more, Heap sort