Pythonクイックソートのみ前半をソートする

Question

私はプリンストンのalgorithm-divide-conquerコースを受けています.3週間目にクイックソートを実装しようとしています。ここで

を実行する準備ができていくつかのテストと私の現在の実装です：私は、結果として[2, 3, 6, 10, 5, 4]を取得array = [3, 5, 6, 10, 2, 4]ためのよう

import unittest 

def quicksort(x): 
    if len(x) <= 1: 
     return x 

    pivot = x[0] 
    xLeft, xRight = partition(x) 
    print(xLeft, xRight) 
    quicksort(xLeft) 
    quicksort(xRight) 
    return x 


def partition(x): 
    j = 0 
    print('partition', x) 
    for i in range(0, len(x)): 
     if x[i] < x[0]: 
      n = x[j + 1] 
      x[j + 1] = x[i] 
      x[i] = n 
      j += 1 

    p = x[0] 
    x[0] = x[j] 
    x[j] = p 
    return x[:j + 1], x[j + 1:] 


class Test(unittest.TestCase): 
    def test_partition_pivot_first(self): 
     arrays = [ 
      [3, 1, 2, 5], 
      [3, 8, 2, 5, 1, 4, 7, 6], 
      [10, 100, 3, 4, 2, 101] 
     ] 

     expected = [ 
      [[2, 1, 3], [5]], 
      [[1, 2, 3], [5, 8, 4, 7, 6]], 
      [[2, 3, 4, 10], [100, 101]] 
     ] 

     for i in range(0, len(arrays)): 
      xLeft, xRight = partition(arrays[i]) 
      self.assertEqual(xLeft, expected[i][0]) 
      self.assertEqual(xRight, expected[i][1]) 

    def test_quicksort(self): 
     arrays = [ 
      [1, 2, 3, 4, 5, 6], 
      [3, 5, 6, 10, 2, 4] 
     ] 

     expected = [ 
      [1, 2, 3, 4, 5, 6], 
      [1, 2, 3, 4, 6, 10] 
     ] 

     for i in range(0, len(arrays)): 
      arr = arrays[i] 
      quicksort(arr) 
      self.assertEqual(arr, expected[i]) 


if __name__ == "__main__": 
    unittest.main() 

...私は私のコードで間違っているものを把握することはできません。それはちょうど良いパーティションですが、結果はオフです...

誰もチップを入れることができますか？ ：） ありがとうございました！

Answer 1

それは問題が正しいものであるクイックソート機能 に常駐し、実際にあなたが を笑っているはずだので、マイナーな問題です：

def quicksort(x): 
if len(x) <= 1: 
    return x 

pivot = x[0] 
xLeft, xRight = partition(x) 
print(xLeft, xRight) 
quicksort(xLeft) 
quicksort(xRight) 
x=xLeft+xRight #this one! 
return x 

何が起こることは、彼らがパイソンこれらxleftから新しいオブジェクトを作成し、xrightされますので、これはもう一つのリスト、START_INDEXを渡すことです （場所ではありません）一つの解であるところ、ソート

に決してなかった、 をEND_INDEXと場所

0123でそれを行います

よくやったフェラ！ 編集： 実際にxleftとxrightを印刷すると完全に実行されていることがわかります:)