Shell Sort: Shell sort is a sorting algorithm. It is an extended version of the insertion sort.

  • In this sorting, we compare the elements that are distant apart rather than the adjacent.
  • We start by comparing elements that are at a certain distance apart. So, if there are N elements then we start with a value gap < N.
  • In each iteration we keep decreasing the value of the gap until the difference becomes 1.
  • In the last iteration, the shell sort acts as an insertion-type.

Complexity table of shell sort

ComplexityBest caseAverage caseWorst case
TimeO(n)O((nlog(n))2)O((nlog(n))2)
Space  O(1)

Algorithm of shell sort

Shell sort example

Suppose you have the following array, which you have to sort.

141819372340293011

The size of array is 9, so n = 9.

Shell Sort in DS

    Now, find the value of the Gap.                             

Gap = floor(n / 2)                                     

= floor (9 / 2)                                     

= floor(4.5)                                     

= 4                

Pass = 1 Gap = 4  

Gap 4 means, if we consider the first element at index 0 then next element will be at index 0+4 = 4., and third element will be at index 4 + 4 = 8.

Shell Sort in DS

 Similarly, if we consider the element at index 1 then next element will be at index 1 + 4 = 5, and third element will be at index 5 + 4 = 9. But there is no 9th index in the above array so we will just have index 1 and 5.

Shell Sort in DS

Similarly, if we consider the element at index 2, 3, and 4 respectively then next element will be at index 2 + 4 = 6, 3 + 4 = 7, and 4 + 4 = 8 respectively.

Shell Sort in DS

  Compare the elements.  

A[0] > A[4] = 14 > 23 // false  

A[1] > A[5] = 18 > 40 // false  

A[2] > A[6] = 19 > 29 // false  

A[3] > A[7] = 37 > 30 // true i.e., swap the both element positions.

Shell Sort in DS

A[4] > A[8] = 23 > 11 // true i.e., swap the both element positions.  

A[1] > A[4] = 14 > 11 // true i.e., swap the both element positions.

Shell Sort in DS

Pass 1 is complete.  

Pass 2: Gap = floor(Gap / 2)            

Gap = floor(4 / 2)  // in pass 1,

Gap was 4.            

Gap = 2  

Gap 2 means, if we consider the first element at index 0 then next element will be at index 0+2 = 2, and similarly this process applied till the end of index.

Shell Sort in DS

Compare the elements.

A[0] > A[2] = 11 > 19 // false

A[]1 > A[3] = 18 > 30 // false

A[2] > A[4] = 19 > 14 // true, i.e. swap the both element positions.

A[1] > A[2] = 11 > 14 // false

Shell Sort in DS

A[3] > A[5] = 30 > 40 //false

A[4] > A[6] = 19 > 29 // false

A[5] > A[7] = 40 > 37 // true, i.e. swap the both element positions.

A[3] > A[5] = 30 > 37 // false

Shell Sort in DS

A[6] > A[8] = 29 > 23 // true, i.e. swap the both element positions.

A[4] > A[6] = 19 > 23 // false

Shell Sort in DS

Pass 2 is complete.  

Pass 3: Gap = floor(Gap/2)             

Gap = floor(2 / 2)  // in pass 2, Gap was 2.             

Gap = 1                 // i.e. last pass when gap is 1, shell sort is like the insertion sort. Compare the elements.

A[0] > A[1] = 11 > 18 // false

A[1] > A[2] = 18 > 14 // true i.e. swap the both element positions.

A[0] > A[1] = 11 > 14 // false

Shell Sort in DS

A[2] > A[3] = 18 > 30 // false A[3] > A[4] = 30 > 19 // true i.e. swap the both element positions. A[2] > A[3] = 18 > 19 // false

Shell Sort in DS

A[4] > A[5] = 30 > 37 // false A[5] > A[6] = 37 > 23 // true i.e. swap the both element positions. A[4] > A[5] = 30 > 23 // true i.e. swap the both element positions. A[3] > A[4] = 19 > 23 // false

Shell Sort in DS

A[6] > A[7] = 37 > 40 // false A[7] > A[8] = 40 > 29 // true i.e. swap the both element positions. A[6] > A[7] = 37 > 29 // true i.e. swap the both element positions. A[5] > A[6] = 30 > 29 // true i.e. swap the both element positions. A[4] > A[5] = 23 > 29 // false

Shell Sort in DS

Pass 3 is complete, and array is fully sorted.

Shell sort program in C language:

Pin It on Pinterest

Share This