<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] |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 traditional way to do qsort in place (ignoring possible variations): def qsort(List, start=0, stop=None): if start >= stop: return if stop == None: stop = len(List) p = partition(List, start, stop) # p = index of pivot/partition item qsort(List, start, p) qsort(List, p+1, stop) where partition puts elements less that pivot value before the pivot value and greater values after. You could instead call your function qSorted to indicate that it returns a sorted copy ;-) Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
