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

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

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: sorting a list using unicodes acending order, no loops, no sort(), using recursion (/thread-34043.html)

Pages: 1 2

sorting a list using unicodes acending order, no loops, no sort(), using recursion - lrn2codee - Jun-20-2021

I'm trying to write a function that sorts a list of ints and letters in acending order (sort using unicode (ord())), using recursion with no loops. I am having trouble and I'm a little stuck. I tried using the code that was answered a while ago:
https://stackoverflow.com/questions/60924751/sort-list-a-into-ascending-order-by-value-using-recursion-instead-of-a-loop-in-p

but that one is using a for loop and works only for ints.

this is what i wrote til now but im getting into an infinite recurse, help please..

def sortlist(lst,n,i):
    
    if (i == n-1):
        if((ord(lst[0]) >= ord(lst[i])) and i>=1):
            lst.insert(0,lst[i])
            del lst[i+1]
        i=0
        return [lst[0]] + [sortlist(lst[1:],n-1,i+1)]
    
    if n>1:
        if((ord(lst[0]) >= ord(lst[i])) and i>=1):
            lst.insert(0,lst[i])
            del lst[i+1]
        
        sortlist(lst,n,i+1)
    else:
        return lst[0]
        

lst = list(input())
n = len(lst)
i = 0
sortlist(lst,n,i)
print("".join(lst))

for this input example:
kd465b21

i will get this output:

Output:
124dk65b

instead of :

Output:
12456bdk

- (right unicode order)

for the code i posted i dont seem to notice the problem that i have, i am a begginer and ill be happy to learn what is my problem.
thank you very much for the helpers and the work is much appericated.
**
i would like to note that the code works for an input such as: 54321 ---> output: 12345
**

sorting a list using unicodes acending order, no loops, no sort(), using recursion - lrn2codee - Jun-21-2021

I'm trying to write a function that sorts a list of ints and letters in acending order (sort using unicode (ord())), using recursion with no loops. I am having trouble and I'm a little stuck. I tried using the code that was answered a while ago:
https://stackoverflow.com/questions/60924751/sort-list-a-into-ascending-order-by-value-using-recursion-instead-of-a-loop-in-p

but that one is using a for loop and works only for ints.

so i worked on it a little but i cant seem to understand why it doesnt worrk for all the length:

def sortlist(lst,n,i):
     if n==1:
        return lst[0]
    
    
    if i<=(n-1):
        if i==(n-1) and n>1:
            i=0
            return [lst[0]] + [sortlist(lst[1:],len(lst)-1,i+1)]
        
        if ord(lst[0])-ord(lst[1+i]) < 0 :
            return sortlist(lst,len(lst),i+1)
    
        if ord(lst[0])-ord(lst[1+i]) >= 0:
            lst.insert(0,lst[1+i])
            del lst[i+2]
            return sortlist(lst,len(lst),i+1)
    


lst = list(input())
n = len(lst)
i = 0
sortlist(lst,n,i)
print("".join(lst))

for this input example:
kd465b21

i will get this output:

Output:
124dk65b

instead of :

Output:
12456bdk

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - Axel_Erfurt - Jun-21-2021

try

in_text = "kd465b21"
in_list = [x for x in in_text]
    
in_list.sort(key=str.lower)

print("".join(in_list))

Output:
12456bdk

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - lrn2codee - Jun-21-2021

(Jun-21-2021, 08:31 AM)Axel_Erfurt Wrote: try

in_text = "kd465b21"
in_list = [x for x in in_text]
    
in_list.sort(key=str.lower)

print("".join(in_list))

Output:
12456bdk

you did not read sir, im trying not to use sort() function,or any loops, im suppoused to use recursion only.
thank you for the effort but it does not help.

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - bowlofred - Jun-21-2021

1) Your function is return()ing information to the caller, but the main program ignores the data that is returned. It just prints the original lst object. If that information isn't necessary, then why are the return statements there? You should be printing the information you got from the function, not the data you called it with. Or you should make sure the function properly sorts the called list (but I don't think it's written to do that).

2) I think what you are trying to do is sort it so the lowest element goes to the front, then sort the rest of the list. So when you recursively call the sort again on line 9, I think you need to start from the beginning (of the now shorter list). So the i needs to be reset to zero for that call.

3) On line 9 sortlist returns a list. On line 3 sortlist returns an element of a list (probably a str the way you've used it). By returning different things, this complicates stuff. I recommend making it always return a list.

4) on line 9 you add two things together. The first is [lst[0]]. This is a list you create with a single element in it. The second is [sortlist(...)]. With step 3 above, this should always be a list. This means you're creating sublists. I think you mean to do something similar to return [lst[0]] + sortlist(...).

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - lrn2codee - Jun-21-2021

(Jun-21-2021, 09:12 AM)bowlofred Wrote: 1) Your function is return()ing information to the caller, but the main program ignores the data that is returned. It just prints the original lst object. If that information isn't necessary, then why are the return statements there? You should be printing the information you got from the function, not the data you called it with. Or you should make sure the function properly sorts the called list (but I don't think it's written to do that).

2) I think what you are trying to do is sort it so the lowest element goes to the front, then sort the rest of the list. So when you recursively call the sort again on line 9, I think you need to start from the beginning (of the now shorter list). So the i needs to be reset to zero for that call.

3) On line 9 sortlist returns a list. On line 3 sortlist returns an element of a list (probably a str the way you've used it). By returning different things, this complicates stuff. I recommend making it always return a list.

4) on line 9 you add two things together. The first is [lst[0]]. This is a list you create with a single element in it. The second is [sortlist(...)]. With step 3 above, this should always be a list. This means you're creating sublists. I think you mean to do something similar to return [lst[0]] + sortlist(...).

explantion:
what i was thinking of doing is, checking if the first unicode is bigger than the next one itll be replaced than i would call the function again but this time itll the check will be with the (i+1) in the list , if "i" reached the list's length itll insert the first character of the list and continue doing this until the length reaches 1 if i has reached 1 it means the last character is the biggest one and itll print it.
obviously somthing is going wrong, i cant understand how to fix it.

im reminding you that im not allowed to use for/while loops only recursion and not supposed to used sort() func. aswell.
to me it seems as if its not checking the last part of the list.

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - Axel_Erfurt - Jun-21-2021

OK, I did not read you will not use loop, maybe this is better

def sortlist(my_list):
    def check_sorted(should_be_sorted, is_sorted):
        new = []
        if len(should_be_sorted) == 0:
            return is_sorted
        else:    
            x = min(should_be_sorted)    
            should_be_sorted.remove(x)
            new.append(x)
            return check_sorted(should_be_sorted, is_sorted + new)
    return check_sorted(my_list, [])


lst = list(input())
print ("".join(sortlist(lst)))

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - Axel_Erfurt - Jun-22-2021

If you have any questions then ask them here and not by private message.

You cannot use for / while loops, sort (), min.

What are you allowed to use at all?

Sounds like this is homework?

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - deanhystad - Jun-22-2021

I doubt this is in the "spirit" of the challenge, but it doesn't call sort or use any loops.

def recursive_sort(items):
    if len(items) > 1:
        min_value = min(items)
        items.remove(min_value)
        return [min_value] + recursive_sort(items)
    return items

It uses a sneak-cheat, borrowing the loop from min(). To make it less of a cheat you could do a recursive min.

def recursive_min(items):
    if len(items) > 1:
        a = items[0]
        b = recursive_min(items[1:])
        return a if a < b else b
    return items[0]

def recursive_sort(items):
    if len(items) > 1:
        min_value = recursive_min(items)
        items.remove(min_value)
        return [min_value] + recursive_sort(items)
    return items

This highlights what you need for a completely recursive solution: Two recursions.

Sorts have two loops; an inner loop to find the lowest or highest remaining value, and an outer loop to split the list into sorted and unsorted values. Sometimes the two are very obvious like the bubbler and index loops in the bubble sort, or the search and insert loops in the insertion sort. Sometimes they can be really difficult to see like the quick but confusing heap sort or quick sort. But there are always two loops. One loop doing the sorting and another loop deciding what to sort.

Knowing that all you are doing is replacing a loop with recursion, you can rewrite (probably) any sort by simply replacing the loops with recursively computing the "loop" indices. Here is a recursive bubble sort.

def recursive_bubble(items, i=None, j=None):
    if i is None:
        i = len(items)-1 # No items are sorted
        j = 0

    if i >= 0:
        if j < i:
            # bubble largest unsorted item to end
            if items[j] > items[j+1]:
                items[j], items[j+1] = items[j+1], items[j]
            recursive_bubble(items, i, j+1)
        else:
            # Move the unsorted/sorted pivot toward the front of the list
            recursive_bubble(items, i-1, 0)

The i "loop" splits the list into sorted and unsorted items. I starts at the end and moves toward the front of the list to eliminate multiple len() calls. The j "loop" is the bubbler. It pushes the largest remaining value toward the end of the list. Two loops. One to sort the remaining values (j) and one to decide which values need to be sorted (i).

Hopefully now you can see why your code does not work. Where are your "loops"? Where is the pivot loop? Where is the sorter loop?

RE: sorting a list using unicodes acending order, no loops, no sort(), using recursion - Axel_Erfurt - Jun-22-2021

(Jun-22-2021, 06:48 PM)deanhystad Wrote: Hopefully now you can see why your code does not work. Where are your "loops"? Where is the pivot loop? Where is the sorter loop?

He said he was not allowed to use loops, sort, min.