QuickSort en Python. Increment dans le problème de tableau

Question

J'essaie d'implémenter le quicksort en python. Le problème est de savoir comment incrémenter/décrémenter la valeur de i/j dans le tableau a. Je sais que je devrais écrire i=i+1 et il n'y a aucune telle chose comme i++ en python, mais je ne comprends pas de quelle façon je devrais le faire. Je suis un novice, voici mon code.

def quicksort(a,lo,hi): 
    if(hi<=lo): 
     return 
    i = lo - 1 
    j = hi 
    v = a[hi] 

    while True: 
     while(a[++i] < v): 
      pass 

     while(v < a[--j]): 
      if(j==lo): 
       break 
     if(i>=j): 
      break 
     t = a[i] 
     a[i] = a[j] 
     a[j] = t 

    t = a[i] 
    a[i] = a[hi] 
    a[hi] = t 
    quicksort(a, lo, i - 1) 
    quicksort(a, i + 1, hi) 

Answer 1

en python, vous ne pouvez pas affecter et obtenir la valeur, c'est une limitation volontaire pour éviter les problèmes avec les fautes de frappe, trouver le point de bon ordre ...

Vous avez pas d'autre choix que de « imiter » le Code C-porté:

while(a[++i] < v): 
     pass 

    while(v < a[--j]): 
     if(j==lo): 
      break 

(noter que les deux constructions génèrent une boucle infinie, car:

++i == i 

et

--j == j 

(application unaire plus un nombre quelconque de fois ou moins unaire un nombre pair de fois donne le même nombre, voir Why Don't Two Plus Operators Throw an Error (e.g., 1 + + 2))

changer donc à:

i += 1 
    while(a[i] < v): 
     i += 1 

    j -= 1 
    while(v < a[j]): 
     if(j==lo): 
      break 
     j -= 1 

Answer 2

ci-dessous La construction ne fonctionne pas de la même manière en Python qu'en C++:

while(a[++i] < v):

ainsi que celui-ci:

while(v < a[--j]):

La façon dont vous modifiez le code est le suivant:

def quicksort(a,lo,hi): 
    if(hi<=lo): 
     return 
    i = lo - 1 
    j = hi 
    v = a[hi] 

    while True: 
     i += 1 
     while(a[i] < v): 
      i += 1 
      pass 

     j -= 1 
     while(v < a[j]): 
      j -= 1 
      if(j==lo): 
       break 
     if(i>=j): 
      break 
     t = a[i] 
     a[i] = a[j] 
     a[j] = t 

    t = a[i] 
    a[i] = a[hi] 
    a[hi] = t 
    quicksort(a, lo, i - 1) 
    quicksort(a, i + 1, hi)