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]
Follow Me
If you like my post please follow me to read my latest post on programming and technology.
