Shell Sort Algorithm and Program in Python

In this article, we will learn about the shell sort algorithm using python. First, we should understand what is sorting. The arranging of elements in a particular order is known as sorting. An efficient method of sorting is shell sort in python. It is derived from the insertion sort algorithm. In this, insertion sort is first applied to the elements that are farther away from each other and then applied to the elements that are at a less separation. This distance or separation between the elements is known as the interval.

Shell Sort Sequences

There are difference sequences you can follow while implementing Shell Sort. Each of these sequence have different fundamental approach and time complexity. Currently, there are 12 known shell sort sequences –

  1. Original Default Sequence: N, N/2, N/4, …, 1 (N/2k)
  2. Frank & Lazarus Sequence: 2*[N/4]+1, …, 3, 1 (2*[N/2k+1]+1)
  3. Hibbard’s Sequence: 1, 3, 7, 15, … (2k-1)
  4. Papernov & Stasevich Sequence: 1, 3, 5, 9, 17, … (2k+1)
  5. Pratt’s Sequence: 1, 2, 3, 4, 6, 8, … (2p*3q)
  6. Knuth’s Sequence: 1, 4, 13, … ([3k -1]/2)
  7. Incerpi & Sedgewick Sequence: 1, 3, 7, 21, 28, …
  8. Sedgewick Sequence 1: 1, 8, 23, 77, … ([4k+3]*[2k-1 + 1])
  9. Sedgewick Sequence 2: 1, 5, 19, 41, …
  10. Gonnet & Baeza-Yates Sequence: max([5*hk-1 -1/11], 1)
  11. Tokuda’s Sequence: 1, 4, 9, 20, .. ([9*(9/4)k-1 -4]/5)
  12. Ciura’s Sequence: 1, 4, 10, 23, 57, …

Original Sequence’s Formula:

Interval can be calculated using this formula.

h=h/2
h : interval (initialized as h)

Knuth’s Formula (Optional Sequence):

Interval can be calculated using this formula.

h= 3**n/2
h : interval (initialized as 1, and n is nth increment)

Algorithm for Python Shell Sort:

  1. Initialize h
  2. Divide the list into sublists each of interval h
  3. Now, use insertion sort to sort these sublists
  4. Repeat the above steps need to be until the list is completely sorted

Illustration:

To implement Shell sort the following steps must be taken:

At first take a list [34,12,20,7,13,15,2,23]

For this example, we are taking h =4

third
Taking h=4 and creating sublist

Now we get the sublist as: [34,13], [12,15], [20,2], [7,23]

For the next step, we will sort these sublists using insertion sort

After first step we get the list as [13,12,2,7,34,15,20,23]

shell sort 2
Taking h=3 and creating sublist

Now we have a new list and we will take the value of h as 3

The sublists that we get are: [13,7], [12,2], [2,15], [7,20], [34,23]

Now we will perform insertion sort in each of these sublist

After this step the list that we will get is: [7,12,2,13,23,15,20,34]

second
Taking h=2 and creating sublist

Now, we will take the value of h=2

The sublists created are: [7,2], [12,13], [2,23], [13,15], [23,20], [15,34]

AFter performing insertion sort on these lists the resultant list will be: [2,12,7,13,20,15,23,34]

first
Taking h=1 and creating sublist

Now we will take h=1 and create the sublists

The sublists created this time are: [2,12], [12,7], [7,13], [13,20], [20,15], [15,23], [23,34]

Now again we will apply insertion sort these individual sublists and the final result that we get will be [2,7,12,13,15,20,23,34]

The final list obtained by following shell sort algorithm
The final sorted list

Source Code for Shell sort in python:

def shell_sort(inp, n):

    h = n // 2
    while h > 0:
        for i in range(h, n):
            t = inp[i]
            j = i
            while j >= h and inp[j - h] > t:
                inp[j] = inp[j - h]
                j -= h

            inp[j] = t
        h = h // 2


inp = [34, 12, 20, 7, 13, 15, 2, 23]
n = len(inp)
print('Array before Sorting:')
print(inp)
shell_sort(inp, n)
print('Array after Sorting:')
print(inp)

Explanation:

shell_sort() function:

  • This function takes a list and its size as parameters
  • The interval ‘h’ is initialized to half the size of the list
  • Now, follow the below steps till the value of h becomes less than zero
    • Iterate the list form h till end
    • Store each element in a temporary variable
    • Compare the elements that are at an interval of h and swap if required
  • Finally, the value of h is updated and the process is continued till the list is completely sorted

Output of shell sort code in python:

Output for shell sort code in python
Output

Time complexity of shell sort:

  • Worst case – O(n2)
  • Best case – O(n*log n)
  • Avergae case – O(n1.25)

The interval selected affects the time complexity of the shell sort algorithm.

Advantages of using Shell Sort:

  • As it has an improved average time complexity, shell sort is very efficient for a smaller and medium-size list
  • The efficiency of shell sort is better than that of insertion sort and almost five times than that of bubble sort

Disadvantages of using Shell Sort:

  • The main disadvantage of shell sort is that it has a complex algorithm
  • Other sorting techniques like merge sort, quick sort and heap sort prove to be more efficient than shell sort
  • As the size of the array becomes large, its performance decreases

Shell Sort In-depth Tutorial Video

Video Tutorial link.

Must Read

Conclusion:

Shell sort does not use the call stack, and since it can be used very little code, it is used in certain libraries like uClibc. Shell sort is also present in the Linux Kernel. The performance of shell sort is better than insertion sort. However, its cache miss ratio is higher than that of quicksort.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

Subscribe
Notify of
guest
2 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Mallika
Mallika
4 months ago

This seems confusing to follow. First, you introduce the formula:

h=h*3+1
h : interval (initialized as 1)

This would suggest h = 1, then h = 4, then h = 13.

However, the illustration takes h = 4,3,2,1 – decrementing by 1 each time.

Then, we come to the code; here, the decrement for h under the condition
while h > 0:
is not h = h-1, but h//2!!

Pratik Kinage
Admin
Pratik Kinage
3 months ago
Reply to  Mallika

Hi,

Shell Sort can be done via multiple sequences. In the code and examples, h/2, h/4, …, 1 is used as a sequence. I’ve edited the post to make it more understandable!
Please let me know if you still have any doubts.

Regards,
Pratik