Sorting troubles

seyensubs at yahoo.com seyensubs at yahoo.com
Mon May 14 12:05:08 EDT 2007


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.




More information about the Python-list mailing list