Shell sort is a highly efficient sorting algorithm and is based on insertion sort algorithm. This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left.
This algorithm uses insertion sort on a widely spread elements, first to sort them and then sorts the less widely spaced elements. This spacing is termed as interval. This interval is calculated based on Knuth's formula as −
where h is interval with initial value 1
This algorithm is quite efficient for medium-sized data sets as its average and worst-case complexity of this algorithm is Ο(nlogn) (depends upon the gap sequence), where n is the number of items. And the worst case space complexity is O(n).
Let us consider the following example to have an idea of how shell sort works. We take the same array we have used in our previous examples. For our example and ease of understanding, we take the interval of 4. Make a virtual sub-list of all values located at the interval of 4 positions. Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 44}
We compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this −
Then, we take interval of 1 and this gap generates two sub-lists - {14, 27, 35, 42}, {19, 10, 33, 44}
We compare and swap the values, if required, in the original array. After this step, the array should look like this −
Finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion sort to sort the array.
Following is the step-by-step depiction −
We see that it required only four swaps to sort the rest of the array.
procedure shellSort()
A : array of items
/* calculate interval*/
while interval < A.length /3 do:
interval = interval * 3 + 1
end while
while interval > 0 do:
for outer = interval; outer < A.length; outer ++ do:
/* select value to be inserted */
valueToInsert = A[outer]
inner = outer;
/*shift element towards right*/
while inner > interval -1 && A[inner - interval] >= valueToInsert do:
A[inner] = A[inner - interval]
inner = inner - interval
end while
/* insert the number at hole position */
A[inner] = valueToInsert
end for
/* calculate interval*/
interval = (interval -1) /3;
end while
end procedure
#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {
int i;
for(i = 0;i < count-1;i++)
printf("=");
printf("=\n");
}
void display() {
int i;
printf("[");
// navigate through all items
for(i = 0;i < MAX;i++)
printf("%d ",intArray[i]);
printf("]\n");
}
void shellSort() {
int inner, outer;
int valueToInsert;
int interval = 1;
int elements = MAX;
int i = 0;
while(interval <= elements/3)
interval = interval*3 +1;
while(interval > 0) {
printf("iteration %d#:",i);
display();
for(outer = interval; outer < elements; outer++) {
valueToInsert = intArray[outer];
inner = outer;
while(inner > interval -1 && intArray[inner - interval]
>= valueToInsert) {
intArray[inner] = intArray[inner - interval];
inner -=interval;
printf(" item moved :%d\n",intArray[inner]);
}
intArray[inner] = valueToInsert;
printf(" item inserted :%d, at position :%d\n",valueToInsert,inner);
}
interval = (interval -1) /3;
i++;
}
}
int main()
{
printf("Input Array: ");
display();
printline(50);
shellSort();
printf("Output Array: ");
display();
printline(50);
return 0;
}
Input Array: [4 6 3 2 1 9 7 ]
==================================================
iteration 0#:[4 6 3 2 1 9 7 ]
item moved :4
item inserted :1, at position :0
item inserted :9, at position :5
item inserted :7, at position :6
iteration 1#:[1 6 3 2 4 9 7 ]
item inserted :6, at position :1
item moved :6
item inserted :3, at position :1
item moved :6
item moved :3
item inserted :2, at position :1
item moved :6
item inserted :4, at position :3
item inserted :9, at position :5
item moved :9
item inserted :7, at position :5
Output Array: [1 2 3 4 6 7 9 ]
==================================================
Data Structures
Data Structures Overview Arrays Linked List Stack Queue Priority QueueExpression parsing
Infix Notation Prefix Notation Postfix notation Notation ConversionHashing
Hash Table and Function Collision ResolutionSearching Techniques
Linear Search Binary Search Interpolation Search Fibonacci SearchSorting
Bubble Sort Bubble Sort in Depth Selection Sort Selection Sort in Depth Insertion Sort Insertion Sort in Depth Shell Sort Merge Sort Quick Sort Quick Sort in Depth Counting Sort Radix Sort Bucket SortTree
Trees and Graphs Binary Tree Types of Binary Trees Binary Search Tree N-ary Tree AVL Tree Red Black Tree Splay tree B tree B+ treeTree Search Traversal Techniques
Breadth First Search (BFS) Depth First Search (DFS) Inorder, Preorder and Postorder TraversalHeaps
Heaps Introduction Binary Heap Heap OperationsTrending
C Programming
Remember to follow community guidelines and don't go off topic.