Introduction

Shell sort algorithm firstly sorts the far away elements and successively decreasing the interval size until it becomes 1. Our task is to sort the array elements using shell sort algorithm.

Program

def sort(arr, n):
    gap = int(n/2)
    while gap > 0:
        for i in range(gap, n):
            ele = arr[i]
            j = i
            while j >= gap and arr[j - gap] > ele:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = ele
        gap /= 2
        gap = int(gap)
ip_arr = [4, 1, 15, 2, 71]
sort(ip_arr, len(ip_arr))
print("The sorted array is :")
for i in range(len(ip_arr)):
    print(ip_arr[i])

Output

Explanation

In the above code, we started with the large interval size (n/2) and then reducing the interval where n is length of array.

1. In our code, we are using shell algorithm original sequence i.e. n/2 , n/4, n/8 ……. 1.
2. In first loop, the element at 0 index is compared to element at n/2 index. If the element at 0 index is greater than element at n/2 index, the values are swapped else it is left as it is.
3. Similarly, all the elements in this interval are compared and sorted.
4. In the second loop, the interval size is reduced i.e. n/4. And the elements in this interval are compared with the elements at index n/4.
5. For interval n/n, the element at interval 1 are sorted. Now all the elements in the array are sorted and returned.