Shell Sort in Python

You have heard the name of Insertion sort, just like that sorting method, the Shell sort algorithm is mainly a variation of Insertion sort. If you want to read you can read here, Insertion sort in Python.

What we do in Insertion sort is we move elements only one position ahead, But this way creates problems, when an element has to be moved far ahead position, then it makes the involvement of large movements.

So Here idea of shell sort comes out that allows an exchange of far elements. In this sorting method, we create the list h-sorted for a large value of h. Then, We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

Implementation of Shell Sort in Python

# Shell Sort Published on Freshlybuilt.com

def shell_sort(input_list):
    # Start with a large gap, then reduce the gap
    gap = len(input_list) // 2
    # Do a gapped insertion sort for this gap size. 
    # First gap elements input_list[0..gap-1] are already in gapped order
    # keep adding one more element until the entire list is gap sorted
    while gap > 0:
        for i in range(gap, len(input_list)):
            # add input_list[i] to the elements that have been gap sorted 
            # save input_list[i] in temp and develop a place at position i 
            temp = input_list[i]
            # shift earlier gap-sorted elements up until the correct 
            # location for input_list[i] is found 
            j = i

            # Sort the sub list for this gap
            while j >= gap and input_list[j - gap] > temp:
                input_list[j] = input_list[j - gap]
                j = j - gap
            # put temp i.e the original input_list[i]
            # in its correct location 
            input_list[j] = temp

        # Reduce the gap for the next element
        gap = gap // 2

    return input_list

def main():
    lst = [8, 17, 3, 9]
    print("Initial Unsorted List:", lst)
    print("After Sorting:", shell_sort(lst))


if __name__ == "__main__":
    main()

Output

Initial Unsorted List: [8, 17, 3, 9]
After Sorting: [3, 8, 9, 17]

Flow Chart of shell sort in Python

Now It’s time for short youtube video of given code 🙂

Some facts about Shell Sort

Note: Above Time complexity is true for above code, For more detail on it read here

If you liked my blog, Please like my post and share it with your friend 🙂