Python Program for ShellSort

Shell Sort is derived from the insertion sort operation. It is one of the efficient methods of sorting. In this tutorial, we will sort an array with help of the shell sort algorithm.

ShellSort - A basic Introduction

ShellSort is an extended version of insertion sort. It starts by sorting items that are far away, then gradually lowers the distance between the components to be sorted. The interval is reduced based on the following sequences used:

Shell Short - Working

The following method will be implemented by shellshort to sort an array:

1. Take a list and define the gap according to your choice
2. Create sublists and sort those on basis of the insertion sort operation.
3. The gap will reduce after every method
4. This process will continue until the gap becomes 0
5. After all processed completed the list will be sorted

Algorithm

As of now, we have a rough understanding of how shellsort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Define a function shell_sort()
2. Pass two parameters array, a
3. Rearrange elements at each a/2, a/4, ... intervals
4. Use insertion sort to sort the sublist
5. Repeat until the gap becomes 0
6. The list is sorted now
7. Print the list

Program for Shell Sort

As discussed above in the algorithm, let us now dive into the programming part of the ShellSort operation influenced by the algorithm.

def shellSort(array, a):

    gap = a // 2
    while gap > 0:
        for i in range(gap, a):
            temp = array[i]
            j = i
            while j >= gap and array[j - gap] > temp:
                array[j] = array[j - gap]
                j -= gap

            array[j] = temp
        gap //= 2


#driver code
array = [9, 1, 8, 2, 7, 3, 6, 4, 5]
print("The original array is:", array)
size = len(array)
shellSort(array, size)
print('Sorted Array is:', array)

The original array is: [9, 1, 8, 2, 7, 3, 6, 4, 5]
Sorted Array is: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Conclusion

In this tutorial, we have performed a ShellSort operation in python to sort an array. The shellsort algorithm doesn't have stability. The average and best time complexity of the shellsort algorithm is O(n log n) and the worst time complexity is O(n²) and the space complexity is O(1).