L'implémentation Python de Quicksort échoue à trier le tableau entier

Question

J'ai le code python ci-dessous pour l'algorithme Quicksort. Le code fonctionne bien jusqu'à ce que tous les éléments vers la droite du pivot soient plus grands que le pivot, auquel cas ils restent non triés.

En théorie, le code doit trier tous les éléments du tableau, mais à ce stade je ne sais pas ce que je suis absent

def swap(array, i, j): 
    temp = array[i] 
    array[i] = array[j] 
    array[j] = temp 

def choosePivotFirstElement(array, left, right): 
    return left 

def partition(array, pivotIndex, left, right): 
     swap(array, pivotIndex, left) #put pivot to the left 
     pivot = array[left] 
     i = left + 1 

    for j in range(left+1, right+1): 
      if (array[j] < pivot): 
        swap(array, i, j) 
        i = i + 1 
    swap(array, left, i-1) #put pivot back to its place 
    return (i-1) #return the position of the pivot 

def qsort(array, left, right): 
     if ((right - left) < 2): 
      return 

     pivotIndex = choosePivotFirstElement(array, left, right) 
     split = partition(array, pivotIndex, left, right) 

     qsort(array, left, split) 
     qsort(array, split + 1, right) 
     return array 

myList = [7,2,5,1,29,6,4,19,11] 
sorted = qsort(myList,0,len(myList)-1) 
print sorted 

cela devrait retourner

[1, 2, 4, 5 , 6, 7, 11, 19, 29]

retourne à la place

[1, 2, 4, 5, 6, 7, 29, 19, 11]

Je suis novice en python, alors je pourrais faire une erreur assez évidente.

Answer 1

Votre code ne ressemble même pas à un code python, vous essayez toujours de traduire quelque chose en python et ce n'est pas une bonne idée.

Habituellement, vous auriez quelque chose comme ça en Python:

def quickSort(arr): 
    #Leftside 
    less = [] 
    #pivot 
    pivotList = [] 
    #rightside 
    more = [] 
    #if the length of the array is one. then, there is no point in sorting it 
    if len(arr) <= 1: 
     return arr 
    else: 
    #sorting :) 
     #Defines the pivot as the first element 
     pivot = arr[0] 
     for i in arr: 
      #for each element in the array verify: 
      if i < pivot: 
       less.append(i) 
      elif i > pivot: 
       more.append(i) 
      else: 
       pivotList.append(i) 
     #Define the Lists less (left side) and more (right side) 
     less = quickSort(less) 
     more = quickSort(more) 
     #Return the actual array 
     return less + pivotList + more 

a = [7, 2, 5, 1, 29, 6, 4, 19, 11] 
a = quickSort(a) 
print a 

EDIT

Il y a plusieurs erreurs dans votre code comme indiqué par les commentateurs:

Vous devriez pas un swap fonction, comme vous pouvez le faire

array[i], array[j] = array[j], array[i] 

Puisque vous n'appelez pas dans cet exemple, choisissezPivotLastElement ou choisissezPivotMedianofThree, vous ne devriez donc pas les publier. Vous pourriez poser des questions sur des choses spécifiques plus tard, dans d'autres questions. Veuillez lire le How to Create a Minimal, Complete and Verifiable Example avant de poster.

La gamme devrait être plage (gauche + 1, à droite + 1):

Et j'ai une impression que:

if ((right - left) < 2) devrait être quelque chose comme je l'ai utilisé dans mon code: if len(array) <= 1:

Plus tard dans votre code, vous pouvez voir que vous ne définissez pas d'autres listes, et vous ne renvoyez rien. S'il vous plaît, regardez à nouveau mon code et essayez de le comprendre. Vous pouvez poser des questions sur des détails spécifiques, mais vous devriez vraiment essayer de le comprendre.