Shell Sort in Python | Implementation

This tutorial will teach you how to implement Shell Sort on a list of numbers using Python.

I am sure you must be quite familiar with Insertion Sort. If not, you can check out the link below:-

How to perform Insertion Sort in Python ?

So, Shell Sort is nothing but a variation of Insertion Sort. The main difference lies in the fact that in Insertion Sort, we shift elements by only one position. But, in Shell Sort, we shift elements by more than one position in one go.

In Shell Sort, we make the list n-sorted for a large value of n. Then we repeatedly decrement the value of n up until n becomes 1. When this happens, our list is sorted.

So, now that we know what Shell Sort is and how it works, let’s begin.

Python Code: Shell sort

def Shell(a): 
  
    # We count the length and then start with a large interval
    
    length = len(a) 
    interval = int(length/2)
  
    '''
    We perform insertion sort on this large interval.
    Then, we reduce the interval again and again using a while loop.
    '''

    while (interval > 0): 
  
        # Insertion Sort
        
        for i in range(interval,length): 
  
            temp = a[i] 
  
            j = i 
            while(j >= interval and a[j - interval] > temp): 
                a[j] = a[j-interval] 
                j -= interval 
  
            a[j] = temp
            
        # Making interval smaller
            
        interval = int(interval/2)  
  
 # Main Function   
    
if __name__=="__main__":
    
    print("Enter a list of numbers seperated by a space :- ")
 
    ip = list(map(int,input().split()))
    
    print ("Original List :- ") 
    
    for i in range(len(ip)): 
        print(ip[i]), 
      
    Shell(ip) 
      
    print ("\nList After Sorting :- ")
    
    for i in range(len(ip)): 
        print(ip[i])

In the main function, first, we take a list of numbers as input from the user. Then, we call the Shell function to begin the process of Shell Sort.

In the Shell function, we first create a big interval equal to half of the list. Then we enter a while loop and then repeatedly perform Insertion Sort until the interval becomes zero. We decrease the value of the interval before the beginning of each iteration.

OUTPUT

Enter a list of numbers seperated by a space :- 

7 18 1 45 6 9 100 0
Original List :- 
7
18
1
45
6
9
100
0

List After Sorting :- 
0
1
6
7
9
18
45
100

  ANALYSIS OF SHELL SORT

In this implementation of Shell Sort, the time complexity is O(n^2). Although it is the same as Insertion Sort, it performs better when it comes to real-life scenarios when we have to swap elements that are very far away.

CONCLUSION

To learn more about sorting algorithms in Python, you can refer to the links below:-

How to implement Quicksort algorithm in Python

How to implement Topological Sorting in Python