More pythonic shell sort?

[John Machin]

On 10/06/2006 7:00 AM, akameswaran at gmail.com wrote:
> 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.

Slicing? I don't see any, and besides you don't want to be copying 
chunks of your list anyway -- see below.

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

Not exactly stand-alone, if it needs another sort for its initialisation :-)

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

Use xrange instead of range, to save memory.

>                 self.gapInsertionSort(myList,i,gap)
> 
>     def gapInsertionSort(self,theList,start,gap):

Having a method call here will slow it down somewhat.


>         for i in range(start,len(theList),gap):
>             j = i
>             curElem = theList[j]
>             while (j > 0) and (theList[j-gap] > curElem):

I think that you mean "while j >= gap" ... otherwise theList[j-gap] will 
be using Python's wrap-around negative subscripting to access something 
at the other end of the list! And you'll never know, because the last 
pass with gap == 1 will (laboriously) clean up any mess. You should 
instrument your code with counts of comparisons and rearrangements, and 
compare those with examples from the textbooks and the literature *AND* 
your pencil-and-paper experiments with a gap-list of (say) [5, 1] on a 
small number of elements.

>                 j -=gap                            # undocumented
> feature??
>             if j!=i:
>                 theList.insert(j,theList.pop(i))
>                 theList.insert(j+gap,theList.pop(j+1))

Quadruple yuck. Each pop() and insert() could involve moving many list 
elements unnecessarily. It's not "pythonic" to use advanced language 
features when they are inefficient for the job at hand. All you need is 
len(alist), alist[i] = value, and value = alist[i]. A simple translation 
of a shellsort written in C would do the job admirably.

Perhaps to Pythonise your mind you should try an object-oriented example 
-- one that truly needs a class or two; your shellsort doesn't really 
need a class (that's your Java background shining through!).

HTH,
John