Попытка сделать сортировку Gnome рекурсивной

Question

Мне дали следующий блок кода

def sort(a): """Sort list a into ascending order by value. Adapted from https://en.wikipedia.org/wiki/Gnome_sort#Code. """ pos = 0 while pos < len(a): if pos == 0 or a[pos] >= a[pos-1]: pos += 1 else: a[pos], a[pos-1] = a[pos-1], a[pos] pos -= 1

, и мне нужно сделать то же самое в python, но рекурсивно, а не итеративно. пока у меня есть

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

Может кто-нибудь помочь мне

Answer 1

Вы не должны возвращаться, когда pos меньше len(a), и вы должны сделать рекурсивный вызов с pos - 1 после замены:

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