Sorting troubles

[Thomas Nelson]

On May 14, 11:05 am, seyens... at yahoo.com wrote:
> 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(List)):
>         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.

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.
HTH,
Tom