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/2^k)
2. Frank & Lazarus Sequence: 2*[N/4]+1, …, 3, 1 (2*[N/2^k+1]+1)
3. Hibbard’s Sequence: 1, 3, 7, 15, … (2^k-1)
4. Papernov & Stasevich Sequence: 1, 3, 5, 9, 17, … (2^k+1)
5. Pratt’s Sequence: 1, 2, 3, 4, 6, 8, … (2^p*3^q)
6. Knuth’s Sequence: 1, 4, 13, … ([3^k -1]/2)
7. Incerpi & Sedgewick Sequence: 1, 3, 7, 21, 28, …
8. Sedgewick Sequence 1: 1, 8, 23, 77, … ([4^k+3]*[2^k-1 + 1])
9. Sedgewick Sequence 2: 1, 5, 19, 41, …
10. Gonnet & Baeza-Yates Sequence: max([5*h_k-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

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]

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]

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]

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]

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:

Time complexity of shell sort:

• Worst case – O(n²)
• Best case – O(n*log n)
• Avergae case – O(n^1.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

• Insertion Sort in Python [Program, Algorithm, Example]
• Understanding Python Bubble Sort with examples

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!