Sorting troubles

[seyensubs]

I have the following implementations of quicksort and insertion sort:

def qSort(List):
if List == []: return []
return 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]])

def insertSort(List ):
for i in range(1,len(Lis t)):
value=List[i]
j=i
while List[j-1]>value and j>0:
List[j]=List[j-1]
j-=1
List[j]=value

Now, the quickSort does not modify the original list, mostly because
it works on products and concatenations, rather than alterations.
The insertion sort, however, does modify the list. Now, to give
results, they should be called in such a way( A is an unsorted list)
A=qSort(A)
# the insertion sort does not require this,
insertSort(A)

I would like to know how can I modify the qSort function such that it
affects the list directly inside
I have tried doing it like this

def qSort(List):
if List == []: return []
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

while processing, the list changes, but those changes remain inside
the function, so that once it's over, if nothis catches the return,
the original List remains unchanged.

If not a solution, I would like to at least know why it does what it
does. I so understand that List(above) is only a reference to the
actual data(a list), but I'm not passing a copy of the data to the
function, but the actual reference(hence , insertSort does
modifications). But then how can I change, inside the function, the
object List is referencing to? If I can't modify the original list,
maybe I can make the variable List point to another list? But changes
inside the function are local. Sorry if this is a bit confusing.

[Aether.Singularity]

On May 15, 11:54 am, Steven D'Aprano
<ste...@REMOVE. THIS.cybersourc e.com.auwrote:

On Mon, 14 May 2007 21:45:26 -0700, seyensubs wrote:

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.

Teach may have been thinking of languages where comparing items is fast
and moving data is slow; Python is the opposite, comparisons invoke a
whole bucket-full of object-oriented mechanism, while moving data just
means moving pointers.

It needs to be said, just in case... this is a good learning exercise,
but don't use this in real code. You aren't going to get within a bull's
roar of the performance of the built-in sort method. Tim Peter's
"timsort" is amazingly powerful; you can read about it here:

http://pythonowns.blogspot.com/2002_...chive.html#797...

http://svn.python.org/projects/pytho...s/listsort.txt

--
Steven.

Yeah, I know any stuff your average CS student will crank out is way
below anything in-built in the core language and libraries. After all,
smart, experienced people worked on those a lot more than me on
these :)

The blog post is dead, but the .txt is alive(it's the svn of
python.org, after all). Gonna read it but looks a bit beyond my level
of comprehension, for now anyway.

Thanks for all the answers! ..oh, got a 10(out of 10) points in class
for the program. Writing stuff in a language no one else learns at the
university and doing 5 versions of quickSort to test performance
must've paid off. Thanks again :)