Discussion :

[ImmoTPA]

Bonjour,

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

Voici mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Jedai]

Je te propose une petite expérience :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[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, il faut donc reconstruire ce tableau ?

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

[Jedai]

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.

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

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] !

--
Jedaï

[ImmoTPA]

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