Thanks for the critique. John Machin wrote: > On 10/06/2006 7:00 AM, [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
