-1

How to sort a list into ascending order by value using recursion instead of a loop in python? For example, to sort [2,0,1] to [0,1,2].

def sort(a):  

    pos = 0
    if pos == 0 or a[pos] >= a[pos - 1]:
        pos += 1
        return sort(a)
    else: 
        a[pos], a[pos-1] = a[pos-1], a[pos]
        pos -= 1
        return sort(a)

Here is what I wrote and I know it does not work because the pos is always equal to 0 at first. How could I fix it?

I test the code below. enter image description here

user13150760
  • 1
  • 2
  • 2
    Imagine that you had someone else's `sort` function to use, instead of making recursive calls. Could you think of a way to use that `sort` function on some sub-list (or sub-lists), and combine the results to get a sorted list? All you do is write that, and then realize that you can make recursive calls instead of using the external function - because it does the same thing. – Karl Knechtel Mar 30 '20 at 05:59

1 Answers1

0

Based on this answer, Quick sort is an example of recursive sorting algorithm and can be implemented in Python like this:

def quick_sort(l):
    if len(l) <= 1:
        return l
    else:
        return quick_sort([e for e in l[1:] if e <= l[0]]) + [l[0]] +\
            quick_sort([e for e in l[1:] if e > l[0]])
Jarek Danielak
  • 394
  • 4
  • 18