#1
  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)" :
    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:
    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. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2012
    Location
    39N 104.28W
    Posts
    157
    Rep Power
    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.
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,703
    Rep Power
    480
    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 11:56 AM. Reason: oops, submit pressed accidentally.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo