There were some comments on the previous post about using a limited number of bubble sort runs, as opposed to a full sort of the whole list weighted by original position, which was an appealing argument in a Keep-It-Simple-Stupid kind of way.
So I'm running some performance tests comparing limited bubblesorting of lists against a decorated sort weighted by initial position. Here is the code tested:
# This is run on the data eight times by the testing code
skip = False
for a in xrange(len(sortlist)-1):
if skip == False:
if sortlist[a] > sortlist[a+1]:
temp = sortlist[a]
sortlist[a] = sortlist[a+1]
sortlist[a+1] = temp
skip = True
skip = False
templist = zip(sortlist,range(len(sortlist)))
declist = [(item+(item/4),item) for item in templist]
return [item for item in declist]
In performance tests on lists of 3200 random small integers, the decorated sort runs from 40-60% faster than the bubblesort, despite it creating three entirely new lists along the way.
decsortundec uses list comprehensions, which are a powerful, yet to me somewhat confusing, aspect of the language. To my understanding they are a way of creating a new list from a source list quickly, and along the way you can modify each item of the original list and/or choose whether to include it or not. Note that this code runs in Python 2.7; Python 3 list comprehensions create iterators instead of lists, so the return value must be explicitly turned into a list, using list(). (There might be a better way to do this, in Python 2, using functional programming, but my brain hasn't been twisted into thinking in that particular Lispy way yet.)
1. bubblepass is not a pure bubble sort, because on our trip through the list we skip positions that have already been swapped from the previous position. That doesn't matter in a true bubble sort where we're ultimately trying to sort all the items as quickly as possible, but we'd need it here since we specifically don't want particular items to travel far.
2. It is possible that PyPy will optimize the bubblesort better, maybe far better, since it uses fairly elementary Python, while the other uses list comprehensions which are mostly implemented in C by the virtual machine.
3. I'm new to writing list comprehensions (which decsortundec uses twice) so it's possible there's a more efficient way to write this. Would anyone know of a better way to factor in an item's original index number into its sorting weight?
4. It might be possible to use some of that list comprehension stuff on the bubble sort, but I don't see how to implement it off the top of my head.