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

I wrote down this code and it works but when I convert it to .py and try to run it with an input, I will write down that recursion has reached limit or something similar.

Note: I'm not using sort(), min(), and other functions, as part of my assignment.

def sortl(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])
    
    sortl(lst, (i + 1), b_ord)

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

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

1 answer

  • answered 2021-06-23 12:00 Mulan

    You do not need to use chr or ord. You can write a simple recursive sort using a insert helper. We will use inductive reasoning to write each function.

    1. if the list is one element or less, return the list
    2. (inductive) there is at least two elements. insert the head, l[0], into the sorted tail, l[1:]
    def sort(l):
      if len(l) < 2:
        return l                          # 1
      else:
        return insert(sort(l[1:]), l[0])  # 2
    

    insert inserts a value into a sorted list -

    1. if the list is empty, return a singleton list of value
    2. (inductive) the list as at least one element. if the list head is less than value to insert, prepend the list head to the recursive sub-problem
    3. (inductive) the list has at least one element and it is larger than the value, prepend the value to the list
    def insert(sorted, value):
      if not sorted:
        return [value]                                  # 1
      elif sorted[0] < value:
        return [sorted[0]] + insert(sorted[1:], value)  # 2
      else:
        return [value] + sorted                         # 3
    
    print(sort([5,3,6,1,4,7,2]))
    print(sort("gebafcd"))
    
    [1, 2, 3, 4, 5, 6, 7]
    ['a', 'b', 'c', 'd', 'e', 'f', 'g']
    

    This is definitely not the best performing sort technique but one that is simple enough to begin to understand recursion