The shell sort improves on the insertion sort by breaking the original list into a number of smaller sub-lists, each of which is sorted using an insertion sort.
The unique way that these sub-lists are chosen is the key to the shell sort. Instead of breaking the list into sub-lists of contiguous items, the shell sort uses an increment i, sometimes called the gap, to create a sub-list by choosing all items that are i items apart.
Resources for Review
Check out the resources below for a review of Shell sort:
def shell_sort(arr): sublistcount = len(arr)/2 # While we still have sub lists while sublistcount > 0: for start in range(sublistcount): # Use a gap insertion gap_insertion_sort(arr,start,sublistcount) sublistcount = sublistcount / 2 def gap_insertion_sort(arr,start,gap): for i in range(start+gap,len(arr),gap): currentvalue = arr[i] position = i # Using the Gap while position>=gap and arr[position-gap]>currentvalue: arr[position]=arr[position-gap] position = position-gap # Set current value arr[position]=currentvalue
arr = [45,67,23,45,21,24,7,2,6,4,90] shell_sort(arr) print(arr)
[2, 4, 6, 7, 21, 23, 24, 45, 45, 67, 90]
If you like my post please follow me to read my latest post on programming and technology.