функция рекурсии, которая принимает список и возвращает отсортированный список

Question

Я работаю над функцией сортировки, которая является функцией рекурсии, которая берет список и возвращает отсортированный список. (Использование рекурсии является обязательным требованием).

def separate(p : callable, l : [object]) -> ([object],[object]): 
    if l == []: 
     return([],[]) 
    else: 
     if p(l[0]): 
      return (separate(p, l[1:])[0]+[l[0]],separate(p, l[1:])[1]) 
     else: 
      return (separate(p, l[1:])[0], separate(p, l[1:])[1]+[l[0]]) 

def sort(l : [object]) -> [object]: 

    z = separate((lambda x: [y > x[0] for y in x]),l) 
    return sort(z[0]) + sort(z[1]) 

отдельная функция передала предикат и список; он возвращает 2-кортеж, индекс 0 которого представляет собой список всех значений в списке аргументов, для которых предикат возвращает True, и индекс 1 которого является списком всех значений в списке аргументов, для которых предикат возвращает False. например:

separate((lambda x:x>=0),[1,-3,-2,4,0,-1,8]) 

возвращает

([1,4,0,8],[-3,-2,-1]) 

вид вызова функции отдельную функцию, чтобы разделить этот список на два списка. функция лямбда в сортировке - это сравнение того, больше ли элемент в списке, чем первый элемент в списке. Затем рекурсивно вызовите сортировку по каждому из этих двух списков и верните один список, содержащий отсортированные значения в первом списке (более мелкие), за которым следует значение, используемое для разделения списка, а затем отсортированные значения во втором списке (более крупные)

сортировка ([4,5,3,1,2,7,6]) будет вызывать отдельные сначала, чтобы вычислить списки [3,1,2] и [5,7,6 ] (обратите внимание, что 4, первое значение в списке, используемое для разделения, не входит ни в один из списков), который при сортировке будет [1,2,3] и [5,6,7], в результате чего возвращается список

[1,2,3,4,5,6,7] 

(4 помещается в список результатов в нужном месте).

Я проверил свою отдельную функцию и работает правильно.

Теперь я пытаюсь написать функцию сортировки, и это показывает, что «INT» объект не итерацию, я добавил ошибку я получил ниже:

29 # Test sort 
30 *Error: sort([1,2,3,4,5,6,7]) raised exception TypeError: 'int' object is not iterable 
31 *Error: sort([7,6,5,4,3,2,1]) raised exception TypeError: 'int' object is not iterable 
32 *Error: sort([4,5,3,1,2,7,6]) raised exception TypeError: 'int' object is not iterable 
33 *Error: sort([1,7,2,6,3,5,4]) raised exception TypeError: 'int' object is not iterable 
36 *Error: l = sort(l) raised exception TypeError: 'int' object is not iterable 
37 *Error: l -> [8, 5, 9, 4, 29, 28, 11, 19, 7, 15, 25, 6, 12, 10, 22, 17, 21, 3, 27, 23, 1, 20, 13, 2, 30, 16, 26, 24, 18, 14] but should -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] 

Я не знаю, почему я получил эту ошибку, может ли кто-нибудь помочь мне исправить мою функцию сортировки? Большое спасибо.

Answer 1

Во-первых, ваша функция separate() беспорядок. Вы пересчитывать separate(p, l[1:]), просто индексировать в два раза, а не использовать локальную переменную:

return (separate(p, l[1:])[0] + [l[0]], separate(p, l[1:])[1]) 

Ваш sort() процедура нуждается в базовый вариант; вы не можете получить первый элемент пустого списка; вы захватываете первый элемент неправильного списка; вы нарушаете логику своей собственной функции функций предикатов, поскольку она обрабатывает весь список вместо одного элемента!

Вот переработан код, который пытается решить вышеуказанные проблемы и очистить стиль немного:

def separate(predicate: callable, array: [object]) -> ([object], [object]): 

    if not array: 
     return list(), list() 

    positive, negative = separate(predicate, array[1:]) 

    if predicate(array[0]): 

     return [array[0]] + positive, negative 

    return positive, [array[0]] + negative 


def sort(array: [object]) -> [object]: 

    if not array: 
     return array # avoid next statement if array is empty 

    first = array[0] 

    lesser, greater = separate(lambda x: x < first, array[1:]) 

    return sort(lesser) + [first] + sort(greater) 


print(sort([4, 5, 3, 1, 2, 7, 6])) 

По желанию, он возвращает:

[1, 2, 3, 4, 5, 6, 7]