Sorting troubles

[Nick Vatamaniuc]

On May 14, 12:05 pm, 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.

It does what it does because in the return statement when you
concatenate qsort(...x<..)+List[0:1]+qsort(...x>=..) you create a new
list. In the insertion sort you modify the values of the list directly
by doing List[j]=List[j-1] or List[j]=value.

If you just have to have the list modified in place, create another
wrapper function that calls your qsort and then will copy all data
from the result into the original list and you are done. Something
like:
def qsort_in_place(L):
   sortedL=qsort(L)
   for (i,x) in enumerate(sortedL):
     L[i]=x

Cheers,
-Nick Vatamaniuc