On May 14, 11:05 am, [EMAIL PROTECTED] 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
--
http://mail.python.org/mailman/listinfo/python-list
