November 30th, 2013, 07:37 AM
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)" :
http://www.youtube.com/watch?v=vxENKlcs2Tw(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:
in theory ,the list should have shrinked till it is empty ,
def partition(lst, start, end):
for j in range (len(lst)-1):
lst= [42,8, 16, 4, 23, 15]
def quick_sort_recursive(lst, start, end):
g=partition(lst, start, end)
d=quick_sort_recursive(lst, start, end)
but as you see, it is an infinite loop.
could you help me fix the problem?
thank you very much for your time.
November 30th, 2013, 08:03 AM
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.
November 30th, 2013, 11:54 AM
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:
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.
>>> print(quick_sort_recursive(, 'unused', 'arguments'))
Quick sort review:
Choose an item from the list. Call it the pivot.
[less than--> <--values greater than or equal to 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 11:56 AM.
Reason: oops, submit pressed accidentally.
[/code] are essential for python code and Makefiles!