# Python Program to Implement Shell Sort Algorithm

«
»

This is a Python program to implement shell sort.

Problem Description

The program sorts a list by shell sort.

Problem Solution

1. Create a generator gaps that takes the size of the list as argument and returns the next element in the sequence of gaps on each successive call. Here the gap sequence chosen is given by 2^k – 1.
2. Create a function shell_sort that takes a list as argument.
3. For each gap returned by gaps, call insertion_sort_with_gap with gap as argument.
4. Create a function insertion_sort_with_gap that takes a variable gap as argument.
5. The function insertion_sort_with_gap performs insertion sort on all elements at a distance of gap from each other. Thus it performs insertion sort on the indexes k, k + gap, k + 2*gap, k + 3*gap, … of the list for all values of k.

Program/Source Code

Here is the source code of a Python program to implement shell sort. The program output is shown below.

```def gaps(size):
# uses the gap sequence 2^k - 1: 1, 3, 7, 15, 31, ...
length = size.bit_length()
for k in range(length - 1, 0, -1):
yield 2**k - 1

def shell_sort(alist):
def insertion_sort_with_gap(gap):
for i in range(gap, len(alist)):
temp = alist[i]
j = i - gap
while (j >= 0 and temp < alist[j]):
alist[j + gap] = alist[j]
j = j - gap
alist[j + gap] = temp

for g in gaps(len(alist)):
insertion_sort_with_gap(g)

alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
shell_sort(alist)
print('Sorted list: ', end='')
print(alist)```
Program Explanation

1. The user is prompted to enter a list of numbers.
2. The list is passed to the shell_sort function.
3. The sorted list is displayed.

Note: Join free Sanfoundry classes at Telegram or Youtube
Runtime Test Cases
```Case 1:
Enter the list of numbers: 5 2 3 1 10
Sorted list: [1, 2, 3, 5, 10]

Case 2:
Enter the list of numbers: 7 6 5 4
Sorted list: [4, 5, 6, 7]

Case 3:
Enter the list of numbers: 2
Sorted list: ```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Take Python Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 