リストを取得してソートされたリストを返す再帰関数

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]) 

別個の関数が述語とリストを渡しました。 0タプルは、述語がTrueを返す引数リスト内のすべての値のリストであり、1インデックスは、述語がFalseを返す引数リスト内のすべての値のリストである2タプルを返します。例えば：

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

戻り

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

ソート機能は、2つのリストにリストを分離するために別の関数を呼び出します。 sortのlambda関数は、リスト内の要素がリスト内の最初の要素より大きいかどうかを比較することです。次に、これら2つのリストのそれぞれに対して再帰的にsortを呼び出し、最初のリスト（小さいもの）にソートされた値を含む単一のリストを返し、その後にリストを区切るための値、2番目のリストのソートされた値（大きいもの）

sort（[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:])を再計算ではなく、ローカル変数を使用します。あなたのsort()ルーチンは基本ケースを必要と

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

を。空のリストの最初の要素を取得することはできません。あなたは間違ったリストの最初の要素をつかんでいます。 1つの要素ではなくリスト全体を処理することで、自分の述語関数の設計のロジックに違反しているのです！

はここで上記の問題を解決し、少しスタイルをクリーンアップしようとするあなたのコードの手直しです：希望通り

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]