Shell sort is a special case of insertion sort. It was designed to overcome the drawbacks of insertion sort. Thus, it is more efficient than insertion sort. In shell sort, we can swap or exchange the far away items in addition to adjacent items.
What is Shell Sort?
In insertion sort, we could move the elements ahead only by one position at a time. If we wish to move an element to a faraway position in insertion sort, a lot of movements were involved thus increasing the execution time. Shell sort overcomes this problem of insertion sort by allowing movement and swap of far-away elements as well.
This sorting technique works by sorting elements in pairs, far away from each other and subsequently reduces their gap. The gap is known as the interval. We can calculate this gap/interval with the help of Knuth’s formula.
Knuth’s formula
Let h be the interval having an initial value = 1
Then, h = h*3 + 1
Characteristics of Shell Sort
- Comparison-based sorting technique.
- Inplace sorting technique just like insertion sort.
- Works very well for medium-sized datasets.
- Unstable sorting technique.
Working of Shell Sort
Suppose we wish to sort the following list of elements: 71, 7, 28, 22, 36, 12, 15, 22, 4.
The first step in shell sort is to decide the gap/interval. Let us take interval = 4. Thus, we will select pairs of elements present at an interval 4 from each other and swap them if they are out of order.
On swapping these pairs, the array will be:
After performing this step, we will simply apply insertion sort on this array.
Iteration 1:
Iteration 2:
Iteration 3:
Iteration 4:
Iteration 5:
Iteration 6:
Iteration 7:
Thus, the final sorted array is:
Shell sort reduces the number of inversions by swapping far away elements in the first step. Hence, it is simply a variation of insertion sort.
Algorithm for Shell Sort
Step 1: Initialize the gap size i.e. h
Step 2: Divide the array into sub-arrays each having interval of h
Step 3: Sort the sub-arrays with insertion sort
Step 4: Reduce the value of h
Step 5: Repeat the above steps until the array is sorted
Pseudo-code of Shell Sort
procedure Shell_sort(Array, n) //n = size of array
while gap < length(Array) /3 :
gap = interval * 3 + 1
END while loop
while gap > 0 :
for (outer = gap; outer < length(Array); outer++):
Insertion_value = Array[outer]
inner = outer;
while inner > gap-1 && Array[inner - gap] >= Insertion_value:
Array[inner] = Array[inner - gap]
inner = inner - gap
END while loop
Array[inner] = Insertion_value
END for loop
gap = (gap -1) /3;
end while loop
END Shell_sort
Shell Sort Implementation in C
#include <stdio.h>
void Shell_sort(int Array[], int N)
{
int gap, j, i, Temp;
for (gap = N/2; gap > 0; gap = gap/2){
for (i = gap; i < N; i++) {
Temp = Array[i];
for (j = i; j >= gap && Array[j - gap] > Temp; j = j-gap){
Array[j] = Array[j - gap];
}
Array[j] = Temp;
}
}
}
void Display_array(int arr[], int n){
for(int i=0; i<n; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
int main(){
int array[]={21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1};
int size =sizeof(array) / sizeof(int);
Shell_sort(array, size);
printf("Sorted array is: \n");
Display_array(array, size);
return 0;
}
Shell Sort Implementation in C++
#include <bits/stdc++.h>
void Shell_sort(int Array[], int N)
{
int gap, j, i, Temp;
for (gap = N/2; gap > 0; gap = gap/2){
for (i = gap; i < N; i++) {
Temp = Array[i];
for (j = i; j >= gap && Array[j - gap] > Temp; j = j-gap){
Array[j] = Array[j - gap];
}
Array[j] = Temp;
}
}
}
void Display_array(int arr[], int n){
for(int i=0; i<n; i++)
cout<< arr[i];
cout << endl;
}
int main(){
int array[]={21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1};
int size =sizeof(array) / sizeof(int);
Shell_sort(array, size);
cout<< "Sorted array is: \n";
Display_array(array, size);
return 0;
}
Implementation of Shell Sort in Java
class ShellSort
{
static void Display_array(int arr[])
{
int N = arr.length;
for (int i=0; i<N; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
int shell_sort(int Array[])
{
int N = Array.length;
for (int gap = N/2; gap > 0; gap = gap/2)
{
for (int i = gap; i < N; i += 1)
{
int Temp = Array[i];
int j;
for (j = i; j >= gap && arr[j - gap] > Temp; j =j- gap)
Array[j] = Array[j - gap];
Array[j] = Temp;
}
}
return 0;
}
public static void main(String args[])
{
int arr[] = {21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1};
System.out.println("Before sorting, the array is: ");
Display_array(arr);
ShellSort ob = new ShellSort();
ob.shell_sort(arr);
System.out.println("Array after sorting: ");
Display_array(arr);
}
}
Shell Sort Implementation in Python
def Shell_sort(Array):
gap = len(Array) // 2
while gap > 0:
i = 0
j = gap
while j < len(Array):
if Array[i] >Array[j]:
Array[i],Array[j] = Array[j],Array[i]
i++
j++
while i - gap != -1:
if Array[i - gap] > Array[i]:
Array[i-gap],Array[i] = Array[i],Array[i-gap]
i = i-1
gap = gap//2
list = 21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1]
print("Input array:",list)
Shell_sort(list)
print("Sorted array is: ",list)
Complexity of Shell Sort
| Scenario | Time complexity |
| Worst case | O(n2) |
| Average case | θ(n log(n)2) |
| Best case | Ω(n log(n)) |
The space complexity of shell sort is O(1).
Applications of Shell Sort
1. Shell sort is a replacement of insertion sort when insertion sort is taking too much execution time.
2. We use shell sort when the call of the stack is overhead.
3. Shell sort is applicable when recursion exceeds a particular limit.
Conclusion
Shell sort is another sorting technique that is highly efficient for medium to large-sized datasets. It is comparison-based and unstable. It helps to reduce the number of operations of insertion sort.
In this article, we have studied what is shell sort, its working and its implementation in various programming languages. We have also seen some real-life applications of shell sort.