Shell sort function

Question

I wrote a Python sort function that uses shell sort:

# 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?

• Caridorc: Try a list comprehension for the sequence.

Answer 1

Shell sort requires 3 loops because of the nature of the algorithm, you can get rid of one looping construct by making a recursive call but there's always loops+recursive calls >= 3. So I don't see how other code you have found uses only 2 loops. The main issue with precomputing the indexes that you are iterating over is that you start to negate one of the best benefits of shell sort, specifically if you do that you no longer have O(1) additional space used You will have fewer loops but you'll get some higher space complexity. Syntactically you might be able to get less levels of indentation with some other approaches but it may not be more readable.

With that said there are a few changes I would make. I'd break out the increment generation into it's own function, taking your code mostly as-is this would become:

def generate_increments_sequence(length):
 """Generate the sequence of increments needed by shellsort
 for a sequence of the given length"""
 e = 2.718281828459
 increment_sequence = []
 counter = 0
 while True:
 counter += 1
 current_value = int(round(e ** (counter - 2)) + 1)
 if current_value >= length:
 break
 increment_sequence.append(current_value)
 return increment_sequence

Now it's worth noting that there's library function for exponentiation math.exp

import math
def generate_increments_sequence(length):
 """Generate the sequence of increments needed by shellsort
 for a sequence of the given length"""
 increment_sequence = []
 counter = 0
 while True:
 counter += 1
 current_value = int(round(math.exp(counter - 2)) + 1)
 if current_value >= length:
 break
 increment_sequence.append(current_value)
 return increment_sequence

You can then use thin in the original function as follows:

def shell_sort(sequence):
 """Sort a sequence using the shell sort algorithm
 :sequence: the sequence to be sorted
 """
 seq_len = len(sequence)
 increment_sequence = generate_increments_sequence(seq_len)
 for incr in increment_sequence:
 # loop through each subset of the sequence
 for j in xrange(incr):
 # loop through each element in the subset
 for k in xrange(j, seq_len, incr):
 guess = k
 # find the correct place for the element
 while guess >= incr and sequence[guess - incr] > sequence[guess]:
 sequence[guess], sequence[guess - incr] = sequence[guess - incr], sequence[guess]
 guess -= incr
 return sequence

The benefit of this is that it starts splitting out the increment generation from the sort generation, which is useful if you are to choose other increment strategies for your shell sort algorithm. If you find that you are calling the sort function a lot of times for the same sequence lengths you can then memoize the results for the generate_increments_sequence functions.

Making that change we get something like this:

def shell_sort(sequence, increment_function):
 """Sort a sequence using the shell sort algorithm
 :sequence: the sequence to be sorted
 :increment_function: function that generates the increment steps
 """
 seq_len = len(sequence)
 increment_sequence = increment_function(seq_len)
 for incr in increment_sequence:
 # loop through each subset of the sequence
 for j in xrange(incr):
 # loop through each element in the subset
 for k in xrange(j, seq_len, incr):
 guess = k
 # find the correct place for the element
 while guess >= incr and sequence[guess - incr] > sequence[guess]:
 sequence[guess], sequence[guess - incr] = sequence[guess - incr], sequence[guess]
 guess -= incr
 return sequence

which we can call with:

sorted_seq = shell_sort(foo, generate_increments_sequence)

Answer 2

nitpicks

• pythonic would be to use ''' docstring ''' for descriptions instead of # comments #
• pythonic would be not to comment the obvious - # initialize the increment sequence for example - it's obvious what you are doing, the why is what is important not the what.
• pythonic is to follow some of the conventions as identified in pep8, such as only one command per line; e.g. not if x is true: y = 1 is frowned upon.

shuttle87 made these changes in his good response, but I hope the above helps you see why his differed from yours.

''' 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
 '''
 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