Pythonの再帰的な挿入ソート関数の予期しない動作

Question

私はPython 2.7で再帰的な挿入ソート関数を書いていました。

最初は、私はそれが機能の再帰としなければならなかった推測エラーTypeError: can only assign an iterable、でしたが、私は私のコードでは特に問題にならないでください：

def recursiveInsertionSort(v): 
    if len(v)!=2: 
     v[0:len(v)-1]=recursiveInsertionSort(v[0:len(v)-1]) 
    i=len(v)-1 
    while v[i-1]>v[i]: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 
     if i==0: return v 

それはだ第二の問題おそらく接続されている。

この場合、私もエラーは表示されませんでしたが（私に教えてください理由がわかっています）、機能はうまく機能しませんでした。

def recursiveInsertionSort(v): 
    if len(v)!=2: 
     recursiveInsertionSort(v[0:len(v)-1]) 
    i=len(v)-1 
    while v[i-1]>v[i] and i>0: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 

私はこの問題を推測として、私は私の間違いを訂正機能を再帰的に使用していました：

def recursiveInsertionSort(v): 
    if len(v)!=2: 
     temp=v[0:len(v)-1] 
     recursiveInsertionSort(temp) 
     v[0:len(v)-1]=temp 
    i=len(v)-1 
    while v[i-1]>v[i] and i>0: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 

しかし、私は本当にあなたが私を助けることができ、これらの2つの動作の原因を理解したいと思います？行うためのよりよい方法があるのなら、私も聞いて

EDIT：あなたの最初の実装と

temp=v[0:len(v)-1] 
recursiveInsertionSort(temp) 
v[0:len(v)-1]=temp 

Answer 1

問題は、ループ内if文でいました。 v[i-1]がv[i]以下であったためにループが終了した場合は、return（これはPythonではreturn Noneと同じです）とは限りません。 TypeErrorは、Noneをスライスに割り当てることができないため、None値が返される再帰呼び出しからのものです。

あなたはwhile文で二つの条件を組み合わせた場合、コードの作業の最初のバージョンを作成し、ループが終了した後、無条件vを返すことができます。

while i > 0 and v[i-1] > v[i]: 
    v[i-1], v[i] = v[i], v[i-1] 
    i -= 1 
return v 

おそらく、この順番に条件をつけなければなりませんあなたの他のバージョンも。

2番目のバージョンが機能しなかった理由は、元のリストをスライスしていて、その内容の部分的なコピーで新しいリストを取得していたことです。次に、あなたの再帰的ソートはそのコピーを修正していました。しかし、外側の関数はスライスされたコピーへの参照を保持していなかったので、変更を見る方法はありませんでした。 3番目のバージョンでは、スライスを新しい変数として明示的に保存することでこれを修正しています。

最後のコードブロックの正確な3行を実行するためのより良い方法はないと思います。

def recursiveInsertionSort(v, i=None): 
    if i is None: 
     i = len(v) - 1 
    if i > 1: 
     recursiveInsertionSort(v, i-1) 
    while v[i-1]>v[i] and i>0: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 

これはあなたの現在のコードよりも少しより効率的になるだろう：あなたはソートする最大インデックスのオプションparaemterを受け入れるように機能を変更した場合しかし、あなたは、すべてのスライスせずに行うことができます各再帰呼び出しのリストはコピーされません。どちらのバージョンもまだO(N**2)ですが、大きなデータセットではquicksortや他のより効率的なソートと競合するとは思わないでください。