I wrote a pythonPython sort function that uses shell sort. Here it is:
# shell sort
# ignore the comments
def shell_sort(sequence):
# shell sort needs an increment sequence
# the increment sequence used here is 1, 2, 4, 8, 21, 56, 149, 404, 1098...
# the sequence is defined by the following equation: round(e^(n-2)) + 1
# initialize the increment_sequence
increment_sequence = []
e = 2.718281828459
counter = 0
while True:
counter += 1
current_value = int(round(e ** (counter - 2)) + 1)
if current_value >= len(sequence): break
increment_sequence.append(current_value)
# loop through the increment sequence
for i in increment_sequence:
# loop through each subset of the sequence
for j in xrange(i):
# loop through each element in the subset
for k in xrange(j, len(sequence), i):
guess = k
# find the correct place for the element
while guess >= i and sequence[guess - i] > sequence[guess]:
sequence[guess], sequence[guess - i] = sequence[guess - i], sequence[guess]
guess -= i
return sequence
The function uses a quadruple nested loop. I think that is overkill, and other (non-Python) code on the Internet only a double loop. On my computer, this is twice as slow as linear insertion. How can I reduce the number of loops?
By the way, this is my first post here. Any suggestions would be more than helpful.
The Turtle
