I want to define a recursive function can sort any list of ints:
def sort_l(l): if l==[]: return [] else: if len(l)==1: return [l[-1]] elif l[0]<l[1]: return [l[0]]+sort_l(l[1:]) else: return sort_l(l[1:])+[l[0]]
Calling this function on a list [3, 1, 2,4,7,5,6,9,8] should give me:
[1,2,3,4,5,6,7,8,9]
But I get:
print(sort_l([3, 1, 2,4,7,5,6,9,8]))--> [1, 2, 4, 5, 6, 8, 9, 7, 3]
Please help me to fix the problem, actual code would be appreciated. Thanks!
Advertisement
Answer
The quick sort is recursive and easy to implement in Python:
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]])
will give:
>>> quick_sort([3, 1, 2, 4, 7, 5, 6, 9, 8]) [1, 2, 3, 4, 5, 6, 7, 8, 9]