Mergesortはもはや返さない

Question

私は初めのpythonコーダーではありませんが、私は先進的なコーナーでもありません。私が何を記述しているかを見ることができれば、問題は説明しやすくなります。ここに問題を見ているコードがあります：

import operator 

def mergeSort(L, compare = operator.lt): 
    if len(L) < 2: 
     return L[:] 
    else: 
     middle = int(len(L)/2) 
     left = mergeSort(L[:middle], compare) 
     right = mergeSort(L[middle:], compare) 
     return merge(left, right, compare) 

def merge(left, right, compare): 
    result = [] 
    i,j = 0, 0 
    while i < len(left) and j < len(right): 
     if compare(left[i], right[j]): 
      result.append(left[i]) 
      i += 1 
     else: 
      result.append(right[j]) 
      j += 1 
    while (i < len(left)): 
     result.append(left[i]) 
     i += 1 
    while (j < len(right)): 
     result.append(right[j]) 
     j += 1 
    return result 

マージ機能が動作します。最終的な返品結果は常に整っています。問題は、mergesortのreturn merge（left、right、compare）に戻り、最終的な戻り結果から一歩前進した場合、返されたリストLはもはや整っておらず、このひどく順序付けられたリストはmergesortを呼び出した関数。なぜこれが起こっているのかわかりません。リターン結果からリターンマージ（左、右、比較）までの復帰旅行で何が起こる可能性がありますか？返されるリストはランダム化されたリストではなく、部分的にソートされたリストのように見えますが、最終的な返り値で完全にソートされました。この結果はmergesortに返されたものではありません。

以前はこのmergesortを問題なく使用していましたので、ソートしているデータに問題がある可能性があります。 Lはリストのリストであり、各リスト要素は、csvに、そして最終的にはExcelにエクスポートされる文字列、すべて同じ長さのリストです。私のデータは、最初の列にはウェブサイトのタイトルを、2番目の列にはURLを持つテーブルです。重複を識別するためにそれらを並べ替えています。完成したテーブルにはいくつかのフィールドがありますが、タイトルとURLの列だけでこの問題を見ることができます。これは簡略化されたものなので、何がうまくいかないかを調べることができます。私は、mergesortがこのデータ構造を扱うことができないかどうかは確かではありませんでしたが、マージの最終結果は確かに可能であることを示しています。しかし、最終的なリターンでは何か不思議なことが起こります。

Answer 1

私はこの問題についてthe python.org listを書いてしまった、と私は頭の上に釘を打ってしまった最初の返信：

木、2016年12月22日には11:55で、デボラ・スワンソンは書きました：

問題は、マージは私が マージソートにマージの確定申告に結果を見て、見ることができ、リストの完璧な順序でLS、 を置き、左と一度戻って右にしながら、 in mergeSort 左半分と右半分が順番に並んでいます。しかし、リストLはまだ元の順序で であり、mergeSortが完了すると、lsはまだ元の順序 になります。たぶん、これを引き起こしているボーンヘッドエラーがあります。 しかし、私はそれを見ることができません。

あなたの分析は優れています。ここでは何が起こるかです：あなたは、並べ替えをマージするとき、あなたは常に（「[：]リターンLの」いずれか、または「結果= []」）新しいリストを返しているが、その後、あなたはこのようにそれを呼び出す：

# sort: Description only, to make hyperelinks & find duplicates 
mergeSort(ls) 

これはmergeSortを呼び出し、新しく並べ替えられたリストを床にドロップします。代わりに、 "ls = mergeSort（ls）"を試してください。

ありがとうございました！

ChrisA

だから、私が今までのわからなかった何かをリストのリストをソートするために、マージソートを使用することが可能です。

Answer 2

マージの結果が保存されていないようです。ここで修正です：

def mergeSort(L, compare = operator.lt): 
    if len(L) < 2: 
     return L[:] 
    else: 
     middle = int(len(L)/2) 
     left = mergeSort(L[:middle], compare) 
     right = mergeSort(L[middle:], compare) 
     L[:] = merge(left, right, compare) 
    return L