444,100 Members | 2,846 Online
Need help? Post your question and get tips & solutions from a community of 444,100 IT Pros & Developers. It's quick & easy.

# Sorting troubles

 P: n/a 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. May 14 '07 #1
10 Replies

 P: n/a On May 14, 11:05 am, seyens...@yahoo.com 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 May 14 '07 #2

 P: n/a On May 14, 12:05 pm, seyens...@yahoo.com 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. It does what it does because in the return statement when you concatenate qsort(...x<..)+List[0:1]+qsort(...x>=..) you create a new list. In the insertion sort you modify the values of the list directly by doing List[j]=List[j-1] or List[j]=value. If you just have to have the list modified in place, create another wrapper function that calls your qsort and then will copy all data from the result into the original list and you are done. Something like: def qsort_in_place(L): sortedL=qsort(L) for (i,x) in enumerate(sortedL): L[i]=x Cheers, -Nick Vatamaniuc May 14 '07 #3

 P: n/a I see. I figured that list comprehensions made another list(duh), but I thought I could relink the object(List) to the new list and keep it once the function ended. Is it possible to pass a reference(to an object.. Like 'List', basically) to a function and change the reference to point to something created inside a function? Or all data unreturned from a function is lost and no references kept?(The second, I'd guess, since it's local temporary scope, but you never know, maybe Python can :) ) May 14 '07 #4

 P: n/a =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 May 14 '07 #5

 P: n/a se*******@yahoo.com wrote: I see. I figured that list comprehensions made another list(duh), but I thought I could relink the object(List) to the new list and keep it once the function ended. Is it possible to pass a reference(to an object.. Like 'List', basically) to a function and change the reference to point to something created inside a function? Or all data unreturned from a function is lost and no references kept?(The second, I'd guess, since it's local temporary scope, but you never know, maybe Python can :) ) Maybe this (untested): def qsort(seq): if seq: pivot = seq.pop() Q = L,R = [],[] for x in seq: Q[x>=pivot].append(x) qsort(R) seq[:] = L+[pivot]+R A. May 14 '07 #6

 P: n/a On Mon, 14 May 2007 09:49:56 -0700, Thomas Nelson wrote: 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. A better way of spelling that would be: def qSortHelp(List): List[:] = qSort(List) return List but the helper function is redundant, as it is easy enough to make the qSort function behave the same way. We can also make the code a smidgen more concise by reversing the sense of the test at the start of the code: def qSort(List): if List: 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 -- Steven. May 15 '07 #7

 P: n/a On May 15, 5:35 am, Steven D'Aprano =List[0]]) return List -- Steven. Ah, I see, just slicing it like that.. nice! But after doing some timing tests, the version that's in place and using partitions is about twice faster than the non hybrid qSort. The hybrid one, with insertionsSort used for smaller lists works faster, but in a weird way. When given lists of 2000, the best bet to is to set the threshold to 14, but when given a list of 40000, 14 is slow, but a threshold of 200(less or more is slower, again) makes it about 8 times faster than a normal qSort, and 4 times faster than an in-place qSort, using a self -defined partitioning alg. Making a hybrid out of the in-place partitioned qSort makes it a bit faster, but not by much compared to the other hybrid which uses list comprehensions. Teach said that the optimal threshold in hybrids is 14-16, but guess he wasn't so right after all =\\ The overhead of using insertion sort on a longer list turns out to be faster than just piling on recursions, when confronted with bigger lists. I should probably try and make it iterative now, see how it goes. Gonna need a stack though, I think. Thanks for all the answers up to now! :) May 15 '07 #8

 P: n/a

 P: n/a On Mon, 14 May 2007 21:45:26 -0700, seyensubs wrote: Ah, I see, just slicing it like that.. nice! But after doing some timing tests, the version that's in place and using partitions is about twice faster than the non hybrid qSort. The hybrid one, with insertionsSort used for smaller lists works faster, but in a weird way. When given lists of 2000, the best bet to is to set the threshold to 14, but when given a list of 40000, 14 is slow, but a threshold of 200(less or more is slower, again) makes it about 8 times faster than a normal qSort, and 4 times faster than an in-place qSort, using a self -defined partitioning alg. Making a hybrid out of the in-place partitioned qSort makes it a bit faster, but not by much compared to the other hybrid which uses list comprehensions. Teach said that the optimal threshold in hybrids is 14-16, but guess he wasn't so right after all =\\ The overhead of using insertion sort on a longer list turns out to be faster than just piling on recursions, when confronted with bigger lists. Teach may have been thinking of languages where comparing items is fast and moving data is slow; Python is the opposite, comparisons invoke a whole bucket-full of object-oriented mechanism, while moving data just means moving pointers. It needs to be said, just in case... this is a good learning exercise, but don't use this in real code. You aren't going to get within a bull's roar of the performance of the built-in sort method. Tim Peter's "timsort" is amazingly powerful; you can read about it here: http://pythonowns.blogspot.com/2002_....html#79780508 http://svn.python.org/projects/pytho...s/listsort.txt -- Steven. May 15 '07 #10

 P: n/a On May 15, 11:54 am, Steven D'Aprano

### This discussion thread is closed

Replies have been disabled for this discussion.