More pythonic shell sort?

[akameswaran at gmail.com]

Thanks for the critique.

John Machin wrote:
> 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.

That was two of the other sort implementations I tried - far uglier
than this.  there were sorts 1-3.  And while I liked the idea of using
the list manipulations built into python - they absolutely were
horrible for this.  I was almost tempted to post that as well - but it
really was an abomination.

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

for large sorts, yeah xrange is good.  with the runs I was doing, it
was irrelevant

>
> >                 self.gapInsertionSort(myList,i,gap)
> >
> >     def gapInsertionSort(self,theList,start,gap):
>
> Having a method call here will slow it down somewhat.

true enough, performance wasn't a consideration on this one


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

good catch on that one.   Didn't think about it.  and with the low
probability of it happening it WOULD have been missed - doh.   The
versions I was running were instrumented - but took that out for
clarities sake.    However j>= gap would not work - say on the first
run where gap should be N/2 (just the worst case) but obviously the
first elements would never get sorted.  .  An additional test for j-gap
>0 would suffice.

>
> >                 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.
>
I didn't really think of pop and insert as advanced features.  But it
was part of my goals to use features that exist in python - remembering
that they are python lists, not funky arrays.
As far as C goes, that was shellSorter1.   Since performance wasn't my
goal - I rather liked the expresiveness of the pop and insert.  makes
it almost read like a book.

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

True enough - java is hard to break sometimes.  I was tempted to add
some try catches just for fun too.  I've written quite a bit that is
more complex - then I get caught in just making it work.  Hence the
point of writing simple well understood problems.  
 
> HTH,
> John