0

私はPythonでクイックソートを実装しようとしています：

def partition(ls):
  if len(ls) == 0:
    return 0
  pivot = ls[0]
  i = 0
  j = 1
  while j < len(ls):
    if ls[j] <= pivot:
      i += 1
      temp = ls[i]
      ls[i] = ls[j]
      ls[j] = temp
    j += 1
  ls[0] = ls[i]
  ls[i] = pivot
  return i

assert(partition([1,2]) == 0)
assert(partition([3,2]) == 1)
assert(partition([3,2,1,4,5]) == 2)
assert(partition([]) == 0)
assert(partition([45]) == 0)

def sort(ls):
  if len(ls) == 0:
    return
  pivotIndex = partition(ls)
  sort(ls[0:pivotIndex])
  sort(ls[(pivotIndex + 1):len(ls)])

ls = [54,1,3,2,4,3,5,4]
sort(ls)
print ls

私のassertステートメントに基づいて、パーティションアルゴリズムが正常に機能することがわかりました。

しかし、私のソート関数は誤った結果を返します。このコードスニペットは印刷されます

[4, 1, 3, 2, 4, 3, 5, 54]

ソートするための再帰呼び出しの境界は何である必要がありますか？サブリストをピボットの左側に、サブリストをピボットの右側に分割することを目指しています。どちらにもピボット自体は含まれていません。

4

2 に答える 2

0 
sort(ls[0:pivotIndex])
sort(ls[(pivotIndex + 1):len(ls)])

スライスはリストの一部をコピーするため、再帰呼び出しでは、元のリストを変更しません。したがって、最初のリストのみがpartitionリストを変更します。

于 2012-06-23T22:27:47.690 に答える
0

クイックソートを含む、オプションのCythonを使用したPythonでのいくつかの既知のソート。ところで、パフォーマンスの比較を確認してください。クイックソートは組み込みのティムソートほど魅力的ではないことに気付くでしょう： http ：//stromberg.dnsalias.org/~strombrg/sort-comparison/

于 2012-06-23T23:54:27.417 に答える