More pythonic shell sort?

[John Machin]

On 11/06/2006 1:26 PM, akameswaran at gmail.com wrote:
> Thanks for the critique.
> 
> John Machin wrote:
>> On 10/06/2006 7:00 AM, akameswaran at gmail.com wrote:
[snip]
>>>     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):

[some other comments and responses snipped above, to show the relevant 
code in one piece]

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

I don't understand your response. Let len(theList) == N and assume that 
the first gap is N/2. The first time that gapInsertionSort is called, 
start will be 1 and gap will be N/2.
Loop index i becomes start i.e. 1.
j becomes 1.
while (j > 0) [True, must test the other part of the "and"] and
... (theList[j-gap] > curElem) *BUT* the subscript is 1-(N/2) which is 
negative and thus will wrap around and cause an utterly meaningless 
comparison.

In fact it will happen the first time in gapInsertionSort for any gap > 
1. In one trial I did sorting list('qwertyasdfgzxcvb') (i.e. N == 15) it 
made 20 meaningless comparisons.

Question 1: What do you mean by "the low probability of it happening"?

Question 2: I don't understand "obviously the first elements would never 
get sorted", as the last pass with gap == 1 cleans up any errors of 
commission  or omission made by the earlier passes. Could you please 
explain that? Or alternatively can you show your code with the "an 
additional test for j-gap > 0 would suffice" fix applied to it?

Question 3: All implementations and descriptions of shellshort that I 
have found consist of THREE nested loops. This includes Knuth's TAOCP 
and K&R 2nd edition. Yours consists of FOUR nested loops (FIVE if you 
count the looping inside insert() and pop()). Where did you get your 
implementation from?

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

They are relatively advanced compared with subscripting, which is *all* 
that is needed to implement shellsort.

> But it
> was part of my goals to use features that exist in python - remembering
> that they are python lists, not funky arrays.

What kind of arrays are "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.

IMHO, like a book written by James Joyce. :-)

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

Try adding some assertions, like:
     assert 0 <= j-gap < n

> I've written quite a bit that is
> more complex - then I get caught in just making it work.

So it seems. Simple design, testing, desk-checking, testing, *permanent* 
instrumentation, testing, *permanent* assertions, testing, ... all these 
can help :-)

Cheers,
John