1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Posts
15
Rep Power
0

#### Recursion problem

Hello everyone,
I created a code which should work as a quick_sort to a list of numbers,like shown in this video-delete the part"(delete this part)" :

now, I got a little problem with the Recursion part, it is infinite , and I am not sure how to fix it,
this is my code:
Code:
```def partition(lst, start, end):

pos=start

piviot=lst[end]
for j in range (len(lst)-1):
if lst[j]<piviot:
lst[pos],lst[j]=lst[j],lst[pos]
pos+=1

lst[pos],lst[len(lst)-1]=piviot,lst[pos]

return pos

lst= [42,8, 16, 4, 23, 15]
start=0
end=5
def quick_sort_recursive(lst, start, end):
if lst==[]:
return
piviot=lst[end]
g=partition(lst, start, end)
quick_sort_recursive(lst,0,g)
quick_sort_recursive(lst,g,priviot)

return lst
d=quick_sort_recursive(lst, start, end)
print d```
in theory ,the list should have shrinked till it is empty ,
but as you see, it is an infinite loop.
could you help me fix the problem?
thank you very much for your time.
2. I'm really not sure what your recursion is doing but I did notice that you have "priviot" instead of "piviot" in your second internal call.
3. Based on rrashkin's discovery, the infinite recursion happens before the code dealt with the right half of the list. Otherwise you would have found the mistake. The return None statement is wrong:
Code:
```>>> print(quick_sort_recursive([], 'unused', 'arguments'))
None```
Also the second two arguments to quick_sort_recursive are indexes. You passed one of the list data values, piviot. Again, that was an error to which your algorithm will never arrive. We'll correct these three errors and work from there.

Quick sort review:
Code:
`[less than-->    <--values greater than or equal to pivot]`
Choose an item from the list. Call it the pivot.
For each item in the list, if the value is less than the pivot fill it in upward from the low bound.
If bigger, fill it in downward from the high index boundary.
We don't know ahead of time where the upward and downward growing sublists will meet.
Repeat the procedure on the two sub-lists until the size is less than 2.
The resulting list is necessarily ordered.
We need to be careful about which value to choose for next comparison,
and there's another pitfall to avoid as well.
Last edited by b49P23TIvg; November 30th, 2013 at 12:56 PM. Reason: oops, submit pressed accidentally.