Shell sort got its name from its inventor Donald Shell. It is an extension of insertion sort. Shell Sort is used to overcome the drawback of insertion sort.
- In insertion sort, items can shift only by one position at a time. Numerous moves are necessary to move an element to a distant location, increasing the algorithm’s time complexity. But shell sort allows swapping between distant or far-away numbers.
- The distance between two numbers is called gap, and it is formulated by Donald Schell.
- It is a comparison-based sort and an in-place sort.
- Works well for medium-sized arrays.
- It is not a stable sort.
Example –
Let’s say n = 9
Different authors give different formulas to find the gap. Gap is also known as an ‘interval’.
We have 9 indexes and the formula is used to decide which index values can be exchanged or swapped. Now that is called a gap or interval between two indexes.
| Authors | Formulas where i ≥ 1 | Gaps (or Intervals) | Worst-Case Time Complexity |
|---|---|---|---|
Donald Shell (Inventor of Shell Sort) | Floor(n/2^i) | n/2, n/4, … ,1 | Ɵ(n^2) |
Hibbard | 2^i-1 | 1, 3, 7, 15, 31, … | Ɵ(n^(3/2)) |
Knuth | (3i-1)/2, not greater than ceiling(n/3) | 1, 4, 13, 40, … | Ɵ(n^(3/2)) |
Sedgewick, 1982 | 4^i + 3.2^(i-1) + 1, prefixed with 1 | 1, 8, 23, 77, 281, … | Ɵ(n^(4/3)) |
Sedgewick, 1986 | If i is even,
9(2^i - 2^i/2) + 1If i is odd,
8.2^i – 6.2^(i+1)/2+1 | 1, 5, 19, 41, 109, … | Ɵ(n^(4/3)) |
But we are applying Donald Shell’s formula because he was the inventor of shell sort. Whenever a question comes on shell sort, you have to apply Shell’s formula, unless it is given that solve the array using (author name) formula.
Using Shell’s formula, we can determine which items can be swapped and how much of the gap should be maintained. This formula will also say that in iteration 1, gap of the items of the array is floor[n/2].
We know that n = 9, and floor[n/2] = 4.
In that case, index 1 will be swapped with index 5, if it is not in order.
Index 2 will be swapped with index 6 if it is not in order and goes on.
In figure 1, only those items can be swapped which have the same color. Index (1, 5, 9), index (2, 6), index (3, 7), index (4, 8).
Iteration 1
Sort Index (1, 5, 9) by using insertion sort.
Sort index (2, 6) by using insertion sort
Sort index (3, 7) by using insertion sort
Same as previous array because green color values is already sorted.
Sort index (4, 8) by using insertion sort
Iteration 2
According to Shell’s formula, in iteration 2 gap will be floor(n/4).
If n = 9, then floor(n/4) = 2.
Sort index (1, 3, 5, 7, 9) by using insertion sort
Sort index (2, 4, 6, 8) by using insertion sort
Iteration 3
According to Shell’s formula, in iteration 3 gap will be floor(n/8).
If n = 9, then floor(n/8) = 1.
If the shell sort gap is 1, then it’s basically an insertion sort.
Index 1 item is always sorted. The next item is 6.
Compare 8 with 6, 8 > 6, swap (8,6)
Compare 8 with 12, 8 < 12, don’t swap
Compare 12 with 14, 12 < 14, don’t swap
Compare 14 with 32, 14 < 32, don’t swap
Compare 32 with 16, 32 > 16, swap (32, 16)
Compare 32 with 36, 32 < 36, don’t swap.
Compare 36 with 65, 36 < 65, don’t swap.
Compare 65 with 58, 65 < 58, swap (65, 58).
ShellSort(Array[], size, temp)
Input the unsorted array of n items.
- for(i = size/2; i >= 1; i = i/2)
- Â Â for(j = i; j<size; j = j++)
- Â Â Â Â temp = Array[j]
- Â Â Â Â for(k = j; k >= i && Array[k-i] > temp; k = k-i)
- Â Â Â Â Â Â Array[k] = Array[k-i]
- Â Â Â Â Array[k] = temp;
- for(i=size/2; i>=1; i=i/2)
The gap in the array is represented by i variable. So, i = size/2, size/4, size/8, … , 2, 1.
Â
- for(j=i; j<size; j=j++)
An index of the array based on the gap is represented by the j variable.
Â
- temp = Array[j]
Temporary variable for swapping if array is not in order.
Â
- for(k = j; k >= i && Array[k-i] > temp; k = k-i)
Let’s say size = 9 and in the 1st iteration gap is size/2, then integer k is equal to 4. Now we will see two conditions because && (AND operator) is there.
If k >= i,
=> 4 >= 4, true
And Array[4-4] > temp
If it is also true, then array is not sorted, and we will go to the 5th statement to swap.
Â
- Array[k] = Array[k-i]
Swapping between array[4] and array[0].
Â
- Array[k] = temp;
This is not in the for loop. When k value is decreased by k-i term, then the safe value temp is allocated to the array[k].
Â
Program for Shell Sort in C
Â
//Shell Sort
#include <stdio.h>
int main()
{
   int i, j, k, temp, size, array[100];
Â
   //Input array declaration
   printf(“Enter the size of the array : “);
   scanf(“%d”, &size);
  Â
   //Input array initialiazation
   printf(“Enter the %d item of the array : “,size);
   for(i=0; i<size; i++)
   {
       scanf(“%d”,&array[i]);
   }
 Â
   //Shell Sort starts
   for (i=size/2; i>= 1; i=i/2) //Gap in the array is represented by i variable.
   {Â
       for (j=i; j<size; j++) //Indexes with gap are represented by j variable
       {Â
           int temp = array[j]; //Temporary variable for swapping
           for (k=j; k>=i && array[k-i]>temp; k=k-i)
           {
               array[k] = array[k-i]; //If array is not in order then swap
           }
           array[k] = temp;Â
       }Â
   }Â
  Â
   printf(“Sorted Array is : “);
   for(i=0; i<size; i++)
   {
       printf(“%d “,array[i]);
   }
 Â
return 0;
}
Time & Space Complexity of Shell Sort
You have seen in the code or algorithm that 3 for loop are there in a shell sort, and some of you think that its time complexity will be n3. But it is not so large, the reason is that there is a gap in the for loop, and the gap is large.
- In best-case, time complexity is O(nlogn).
- In worst-case, time complexity is O(n2) because compiler has to do several swapping.
- In average-case, time complexity is O(nlog(n)2) basically O(n1.25).
- Space complexity is O(1) because we take a variable temp to save the original value.
Advantages of Shell Sort
- It takes less time in the average case compared to insertion sort.
- Inversion in insertion sort comes from this sort.
Disadvantages of Shell Sort
- It takes more time in the best case compared to insertion sort.
- We use the Donald Schell formula for maintaining the gap, but if indexes are not in order then we use only insertion sort.
Â
Test Yourself
Q1- Shell Sort is an extension of which sorting algorithm?
Merge Sort
Quick Sort
Bubble Sort
Insertion Sort
Ans – (4)
Explanation – Shell Sort is an extension of Insertion Sort, aiming to improve its performance by allowing swapping between distant or far-away numbers.
Q2- What does the “gap” represent in Shell Sort?
The number of elements to be swapped in each iteration
The distance between two numbers to be compared and swapped
The size of the array to be sorted
The number of iterations in the sorting process
Ans – (2)
Explanation – In Shell Sort, the “gap” represents the distance between two numbers that are compared and swapped during each iteration.
Q3- Shell Sort has a time complexity of O(n^2) in which scenario?
Best-case
Average-case
Worst-case
None of the above
Ans – (3)
Explanation – The worst-case time complexity of Shell Sort is O(n^2) when the gap sequence is not very effective, and the array is nearly sorted or in reverse order.
Q4- Which author’s formula is used in Shell Sort to determine the gap sequence by default (n/2, n/4, n/8, … , 2, 1)?
Hibbard
Knuth
Sedgewick
Donald Shell
Ans – (4)
Explanation – The default gap sequence used in Shell Sort is formulated by Donald Shell, who invented the sorting algorithm.
Q5- Shell Sort is most efficient for sorting:
Small arrays
Large arrays
Medium-sized arrays
Already sorted arrays
Ans – (3)
Explanation – Shell Sort performs well for medium-sized arrays as it combines the benefits of Insertion Sort with more efficient gap-based swapping.
Q6- What is the space complexity of Shell Sort?
O(1)
O(n)
O(log n)
O(n^2)
Ans – (1)
Explanation – Shell Sort is an in-place sorting algorithm, meaning it doesn’t require additional memory proportional to the size of the input array.
Q7- Which sorting algorithm is similar to Shell Sort in terms of its best-case time complexity?
Bubble Sort
Insertion Sort
Merge Sort
Selection Sort
Ans – (3)
Explanation: Both Shell Sort and Merge Sort have an best-case time complexity of O(nlogn).
Q8- Shell Sort performs better than Insertion Sort because:
It has a better worst-case time complexity.
It uses fewer comparisons and swaps.
It is a recursive sorting algorithm.
It is an adaptive sorting algorithm.
Ans – (2)
Explanation – Shell Sort’s gap-based approach allows it to perform fewer comparisons and swaps compared to regular Insertion Sort, leading to improved efficiency.
Q9- Shell Sort is considered an in-place sorting algorithm because:
It sorts the elements in their original memory locations.
It uses a constant amount of additional memory for sorting.
It has a stable sorting property.
It adapts to the input order.
Ans – (1)
Explanation – In-place sorting algorithms sort the elements within their original memory locations without requiring significant additional memory.
Q10- Which formula is used to determine the gap sequence in Shell Sort, according to Donald Shell?
Gap = floor(n/2^i)
Gap = 2i – 1
Gap = (3i – 1)/2
Gap = 4i + 3.2i – 1 + 1
Ans – (1)
Explanation: According to Donald Shell’s formula, the gap sequence in Shell Sort is determined as Gap = floor(n/2^i), where n is the size of the array, and i is the iteration number.
