problème Quick sort

Bonjour,

Je remercie par avance tous ceux qui s'intéresseront à mon problème.

Voici mon code :

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 31 32 33 34 35 36 37 38 39 40 41

# *-coding:Utf-8 -* import random   def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp   def chosePivot(A):   return A[random.randint(0, len(A)-1)]     def partition(A, p):   swap(A, 0, A.index(p))   i = 1 j = 1   while j < len(A): if A[j] < p: swap(A, i, j) i += 1 j += 1 swap(A, 0, i-1)   return A.index(p)   def quickSort(A):   if len(A) <= 1: return A   p = chosePivot(A)   r = partition(A, p) quickSort(A[:r]) quickSort(A[r+1:])   return A

---

Ma fonction partition fait le travail comme il faut, et les appels récursifs se font sur les bons sous-tableaux, mais au moment de "raccrocher" tout le monde, j'obtiens n'importe quoi. Quelqu'un peut-il m'expliquer pourquoi ma récursion échoue ?

Merci

Immo

Je te propose une petite expérience :

Code:

---

1 2 3 4 5 6 7 8 9

>>> a = [1,2,3] >>> b = a[:2] >>> b [1,2] >>> b[0] = 100 >>> b [100,2] >>> a [1,2,3]

---

As-tu maintenant une idée d'où vient ton problème ?

Ton expérience semble montrer que lorsque je fais un appel récursif sur un sous-tableau de mon tableau principal, les changements ne sont pas appliqués au tableau d'origine, il faut donc reconstruire ce tableau ?

Dans mon cas je pourrai faire return quickSort(A[:r])+[A[A.index(p)]]+quickSort(A[r+1:])

Citation:

---

Envoyé par ImmoTPA

Ton expérience semble montrer que lorsque je fais un appel récursif sur un sous-tableau de mon tableau principal, les changements ne sont pas appliqués au tableau d'origine,

---

Bien vu. :)

Citation:

---

Envoyé par ImmoTPA

il faut donc reconstruire ce tableau ?

---

C'est une possibilité (inefficace), ou sinon, ton quickSort pourrait prendre des paramètres 'start' et 'end' en plus lui indiquant de ne trier que les éléments aux indices entre 'start' et 'end' (mais ça te complique la tâche, tout dépend donc de l'objectif).

Citation:

---

Envoyé par ImmoTPA

Dans mon cas je pourrai faire return quickSort(A[:r])+[A[A.index(p)]]+quickSort(A[r+1:])

---

Un truc comme ça... Mais [A[A.index(p)]] est une façon singulièrement inefficace de dire [p] ! :roll:

--
Jedaï

Oui en effet, un peu crevé à cette heure jfais n'importe quoi. merci de ton aide à bientôt