On May 15, 5:35 am, Steven D'Aprano <[EMAIL PROTECTED]> wrote: > On Mon, 14 May 2007 09:49:56 -0700, Thomas Nelson wrote: > > The thing is that [x for x in List[1:]...] is a brand new list created > > by iterating over the old one. > > How about: > > qSortHelp(List): > > newlist = qSort(List) > > for i, val in enumerate(newlist): > > List[i] = val > > You have to iterate over one more time, but this sorts the list in > > place. > > A better way of spelling that would be: > > def qSortHelp(List): > List[:] = qSort(List) > return List > > but the helper function is redundant, as it is easy enough to make the > qSort function behave the same way. We can also make the code a smidgen > more concise by reversing the sense of the test at the start of the code: > > def qSort(List): > if List: > List[:] = qSort([x for x in List[1:] if x< List[0]]) \ > + List[0:1] + qSort([x for x in List[1:] if x>=List[0]]) > return List > > -- > Steven.
Ah, I see, just slicing it like that.. nice! But after doing some timing tests, the version that's in place and using partitions is about twice faster than the non hybrid qSort. The hybrid one, with insertionsSort used for smaller lists works faster, but in a weird way. When given lists of 2000, the best bet to is to set the threshold to 14, but when given a list of 40000, 14 is slow, but a threshold of 200(less or more is slower, again) makes it about 8 times faster than a normal qSort, and 4 times faster than an in-place qSort, using a self -defined partitioning alg. Making a hybrid out of the in-place partitioned qSort makes it a bit faster, but not by much compared to the other hybrid which uses list comprehensions. Teach said that the optimal threshold in hybrids is 14-16, but guess he wasn't so right after all =\\ The overhead of using insertion sort on a longer list turns out to be faster than just piling on recursions, when confronted with bigger lists. I should probably try and make it iterative now, see how it goes. Gonna need a stack though, I think. Thanks for all the answers up to now! :) -- http://mail.python.org/mailman/listinfo/python-list
