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()
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
|Best Case Time Complexity||O(n^2)|
|Average Case Time Complexity||O(n^2)|
|Worst Case Time Complexity||O(n^2)|
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 🙂