Re: Sorting troubles

On May 14, 11:05 am, seyens...@xxxxxxxxx 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

.

Relevant Pages

  • Re: Sorting troubles
    ... |I have the following implementations of quicksort and insertion sort: ... | def insertSort: ... | The insertion sort, however, does modify the list. ...
    (comp.lang.python)
  • Re: Using properties
    ... > I have a class with a name attribute, which I want to modify using ... > def getname: ... it no longer works if I modify getname and setname to ...
    (comp.lang.python)
  • Re: Sorting troubles
    ... def insertSort: ... The insertion sort, however, does modify the list. ... I so understand that Listis only a reference to the ...
    (comp.lang.python)
  • Re: modifying source at runtime - jython case
    ... modification in class definition. ... >>> def test: ... You can modify the behaviour of all existing instances of a class, e.g. their methods, by modifying the class itself. ... Any reference to the method on the instance will resolve to the method definition from its class, provided you haven't overwritten the method on the individual instance. ...
    (comp.lang.python)
  • Sorting troubles
    ... I have the following implementations of quicksort and insertion sort: ... def insertSort: ... The insertion sort, however, does modify the list. ...
    (comp.lang.python)