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)
