Python quicksort seulement trier la première moitié

Question

Je prends le cours d'algorithmes-diviser-conquérir de Princeton - 3ème semaine, et en essayant d'implémenter le quicksort.

Voici mon implémentation actuelle avec certains tests prêts à exécuter:

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

donc pour array = [3, 5, 6, 10, 2, 4] je reçois [2, 3, 6, 10, 5, 4] suite ... Je ne peux pas comprendre ce qui ne va pas avec mon code. Il se partitionne très bien, mais les résultats sont éteints ...

Quelqu'un peut-il être impliqué? :) Je vous remercie!

Answer 1

il est en fait si petit problème que vous seriez riez le problème réside dans la fonction quicksort le bon est:

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 

ce qui se passe est python créé un nouvel objet de ces Xgauche et Xdroite ils ont jamais été un l'autre est de passer la liste, la start_index, END_INDEX et de le faire en place

en place tri

c'est donc une solution (ce qui est en place)

bien fait fella! edit: et en fait si vous imprimer xleft et xright vous le verriez fonctionne parfaitement :)