Quicksort python

Bonjour à tous, dans mon cours d’algo je dois réaliser un quicksort en python à l’aide de cette énoncé qui m’indique que je dois travailler avec deux modules:

"partitionner Ce module reçoit en paramètre un tableau d’entiers de taille N et 3 entiers représentant respectivement l’indice du premier élément, du dernier élément (pour repérer la plage d’éléments à trier) et du pivot. Le pivot va représenter l’indice de l’élément qui va servir de référence pour partitionner les valeurs, en mettant d’un côté les valeurs plus petites que le pivot (sans pour autant les trier) et de l’autre les valeurs plus grandes. Le module retourne la valeur du nouveau pivot (qui se situe entre ces 2 groupes de valeurs)."

avec comme instruction:

"Il faut d’abord échanger la dernière case avec la case du pivot. Puis, un indice j initialisé avec l’indice de la première case, permettra de repérer le nouveau pivot. Une boucle faisant varier un i du premier au dernier élément (dernier exclus) va permettre de comparer chaque élément avec le dernier. Si le ième élément est inférieur au dernier, alors il faut échanger le ième avec le jème et incrémenter j. En sortie de boucle, il reste à échanger le jème élément avec le dernier et retourner j qui représente le nouveau pivot"

"triRapide Ce module reçoit en paramètre un tableau d’entiers de N cases ainsi que 2 entiers contenant respectivement les indices du premier et dernier élément (pour délimiter la plage de cellules à trier)."

instruction:

"Après avoir déclaré une variable pivot de type entier, il faut réaliser un test qui servira d’arrêt des appels récursifs. L’arrêt se fait tout simplement quand premier n’est plus inférieur à dernier. Dans le cas contraire, il faut affecter une valeur à pivot, au hasard entre premier et dernier (autant prendre le milieu, mais cela n’a pas une grande importance). Puis il faut valoriser la même variable pivot avec l’appel du module partitionner en lui envoyant les bons paramètres. Après cette affectation, puisqu’un nouveau pivot a été calculé, il suffit d’appeler 2 fois le module triRapide, une fois pour trier du premier à l’élément d’indice pivot-1, une seconde fois pour trier de l’élément d’indice pivot+1 au dernier."

Mon problème est que mon tableau n’est pas ordonné en sortie sauf si j’enlève le pivot dans la fonction partitionner et la partie où je donne comme valeur au pivot la moitié du vecteur ( pivot =(first + last) /2 ) .

mon code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def partitionner(tab,first,last,pivot):
    """
        @param:
        @return:
    """
    last, pivot = pivot, last
    j= first
    for i in range(first,last-1):
        if tab[i] < tab[last]:
            tab[j], tab[i] = tab[i], tab[j]
            j+=1
    tab[j], tab[last] =  tab[last], tab[j]
    return j

def quicksort(tab, first, last):
    """
        @param:
        @return:
    """
    if first < last:
        pivot = (first + last) /2
        pivot = partitionner(tab, first, last,pivot)
        quicksort(tab, first, pivot-1)
        quicksort(tab, pivot+1, last)
    return tab


if __name__ == '__main__':
    tab = [10,9,8,7,22,55,6,5,4,3,2,1,91,23,12,11]
    print quicksort(tab,0,len(tab)-1)

avec comme résultat en sortie : [5, 4, 7, 8, 6, 9, 2, 1, 3, 10, 22, 91, 23, 12, 55, 11]

Comme je suis en première année et que c’est mon premier test de la recusivité, je suis un peu perdu pour faire la trace de mes variables sachant que j’ai vraiment l’impression de respecter l’énoncé à 100%,merci d’avance !

OMG merci d’avoir pris le temps de me corriger, j’apprécie énormément. Maintenant tout marche parfaitement! bien que j’ai relu mon code 500 fois l’erreur au niveau de l’échange de la dernière case avec celle du pivot m’est complètement passé sous le nez haha, et je dois m’habituer à lire la doc ca évitera les problèmes comme pour le range ! encore merci

C’est du C déguisé en python, pourquoi par exemple ne pas utiliser

1
2

index_mid = int(len(tab)/2)
pivot = tab[index_mid]

Pourquoi mettre deux paramètres dans la fonction quicksort ?

C’est bien d’utiliser un langage, mais faut utiliser ses forces

@fred : par ce que si il voulait vraiment suivre la logique python il utiliserait sorted() ou la méthode .sort() des listes. Je suis pas un grand fan de ce genre d’exo en python mais bon si tu le fais, c’est pas ettonant de faire un truc pas très pythonic

je suis entièrement d’accord avec vous mais j’avais comme consigne de suivre précisément les informations données dans la description des modules et non faire des modules à ma convenance