More pythonic shell sort?

akameswaran at gmail.com akameswaran at gmail.com
Fri Jun 9 23:00:30 CEST 2006


Disclaimer - I recognize this is not a practical exercise.  There are
many implementations around that would do the job better, more
efficiently (Meaning in C) or whatever.

I caught some thread about sorting and started thinking about shell
sort.... and as part of my trying to pythonise my mind and break my
java mindset

So I decided to tackle this old school problem with the python mindset.


I played around with some list comprehensions, trying to use slicing
inteligently etc.  Anyway this is what I came up with.  If anyone has
suggestions on a more pythonic way to go (all attempts at using list
comprehensions turned into unruly rubbish quite quickly)  I'd
appreciate the input.    An aside - can anyone tell me where the use +=
and -=  is documented?  it works but I can't find it in my docs.
(don't ask about shellSorters 1 thru 3)

class shellSorter4(object):

    def __init__(self,gapSeq):
        self.gapSeq = gapSeq                      # gap sequences are
notoriously hard to tune
        self.gapSeq.sort(reverse=True)

    def sort(self,myList):
        for gap in self.gapSeq:
            for i in range(1,gap+1):
                self.gapInsertionSort(myList,i,gap)

    def gapInsertionSort(self,theList,start,gap):
        for i in range(start,len(theList),gap):
            j = i
            curElem = theList[j]
            while (j > 0) and (theList[j-gap] > curElem):
                j -=gap                            # undocumented
feature??
            if j!=i:
                theList.insert(j,theList.pop(i))
                theList.insert(j+gap,theList.pop(j+1))




More information about the Python-list mailing list