Python Program to Implement Shell Sort Algorithm

This is a Python program to implement shell sort.

The program sorts a list by shell sort.

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.

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)

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.

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: [2]

Sanfoundry Global Education & Learning Series – 1000 Python Programs.

If you wish to look at all Python Programming examples, go to 1000 Python Programs.