sorting a list using unicodes acending order, no loops, no sort(), using recursion

[lrn2codee]

this is an assignment as i said before....
the code that i wrote down is:

def sortlist(lst, i, b_ord ):
        
    if len(lst) == i:
        return lst
    
    elif b_ord > ord(lst[i]):
        
        lst[i - 1] = lst[i]
        lst[i] = chr(b_ord)
        b_ord = ord(lst[0])
        i = 0
            
            
    else:
        b_ord = ord(lst[i])
    
    sortlist(lst, (i + 1), b_ord)


lst = list(input())
n=ord('0')
i=0

sortlist(lst,i,n)
print("".join(lst))

but it is reaching the limit of recursion, although when i try sorting a string on jupyter notebook it works..
so i need to fix this code...

[Axel_Erfurt]

https://codegolf.stackexchange.com/quest...-recursion

[deanhystad]

It works fine for me. Why are you using the ord() function? Python uses a character's ordinal value when comparing, so there is no need for a conversion. One thing I would change is move the initializer code inside the function to make it easier to use.

def sortlist(lst, i=None, b=None):
    if i is None:
        sortlist(lst, 1, lst[0])
    elif i < len(lst):
        if b > lst[i]:
            lst[i - 1] = lst[i]
            lst[i] = b
            b = lst[0]
            i = 0
        else:
            b = lst[i]
        sortlist(lst, (i + 1), b)

I added some print statements to get a better idea how your sort works and I noticed that it can be quite inefficient.

def sortlist(lst, i=None, b=None, count=None):
    print(lst, i, b, count)
    if i is None:
        sortlist(lst, 1, lst[0], 0)
    elif i < len(lst):
        if b > lst[i]:
            lst[i - 1] = lst[i]
            lst[i] = b
            b = lst[0]
            i = 0
        else:
            b = lst[i]
        sortlist(lst, (i + 1), b, count+1)

Sorting 'kd465b21' calls sortlist() 83 times compared to 36 times for the bubble sort which is already considered really inefficient. The inefficiency results from restarting the loop any time you find a value that is out of order. On the other hand this also means that your sort is the fastest sort in the world if the values are already in sorted order. Sorting lists that are in inverse order is a real killer causing sortlist() to be called 91 times for '87654321'

[lrn2codee]

It works fine for me. Why are you using the ord() function? Python uses a character's ordinal value when comparing, so there is no need for a conversion. One thing I would change is move the initializer code inside the function to make it easier to use.

def sortlist(lst, i=None, b=None):
    if i is None:
        sortlist(lst, 1, lst[0])
    elif i < len(lst):
        if b > lst[i]:
            lst[i - 1] = lst[i]
            lst[i] = b
            b = lst[0]
            i = 0
        else:
            b = lst[i]
        sortlist(lst, (i + 1), b)

I added some print statements to get a better idea how your sort works and I noticed that it can be quite inefficient.

def sortlist(lst, i=None, b=None, count=None):
    print(lst, i, b, count)
    if i is None:
        sortlist(lst, 1, lst[0], 0)
    elif i < len(lst):
        if b > lst[i]:
            lst[i - 1] = lst[i]
            lst[i] = b
            b = lst[0]
            i = 0
        else:
            b = lst[i]
        sortlist(lst, (i + 1), b, count+1)

Sorting 'kd465b21' calls sortlist() 83 times compared to 36 times for the bubble sort which is already considered really inefficient. The inefficiency results from restarting the loop any time you find a value that is out of order. One the other hand this also means that your sort is the fastest sort in the world if the values are already in sorted order. Sorting lists that are in inverse order is a real killer causing sortlist() to be called 91 times for '87654321'

so i didnt understand, the code you posted seems inefficient as well...
how can make it efficient, i believe that this is the cause of my problem.

[deanhystad]

How long is your list? Can you provide a sample list that causes your sort to crash? If the list is too long it will be impossible to sort using recursion without changing the recursion depth limit. My recursive bubble sort is limited to sqrt(1000) or 31 elements in length. No matter how you sort you cannot sort a list greater than 1000 elements.