Sorting troubles

[Terry Reedy]

<seyensubs at yahoo.com> wrote in message 
news:1179158708.433792.127150 at h2g2000hsg.googlegroups.com...
|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