Je suis étudiant en 2e année de DUT, et l'on étudie en ce moment le "tri rapide" d'un tableau d'entiers en python.

On nous a donné une correction mais (il me semble que ?) elle est fausse.

Le but étant de prendre le 1er terme du tableau, de comparer les éléments suivants à ce dernier, si l'on en trouve un qui est supérieur, on cherche l'élément le plus proche de la fin du tableau qui est inférieur au 1er element(on place un indice qu'on décremente tant qu'on ne trouve pas un terme qui correspond pour la recherche), on les échange et ainsi de suite. Enfin échange le premier élément avec le "indice-1" terme du tableau. Puis on re étudie  le tableau en 2 : T[0]..T[indice-1] et T[indice+1] et T[max]. Puis on retrie comme au début. Je ne pense pas avoir été très clair dans ces dernières explications...

Je pense que le code vous éclairera plus :

T=[18,26,13,48,-3,19,7,22,-8,-36,0,12,15,17,38,45]

def TriRapide(T,gauche,droite):
	if (gauche<droite):
		T, k=Placer(T,gauche,droite,PlacePivot(T))
		TriRapide(T,gauche,k-1)
		TriRapide(T,k+1,droite)
		return T


def Placer(T,gauche,droite):
        bas=gauche+1
        haut=droite
        while(bas<=haut):
                while(T[bas]<=T[gauche]):
                        bas+=1
                while(T[haut]>T[gauche]):
                        haut-=1
                if(bas<haut):
                        T[bas],T[haut]=T[haut],T[bas]
                        bas+=1
                        haut-=1
        T[gauche],T[haut]=T[haut],T[gauche]
        return T,haut
                
def PlacePivot(T): #Donne la future place du pivot
    i=1
    place=0
    while(i<len(T)):
        if(T[0]>T[i]):
           place+=1
        i+=1
    return place

TriRapide(T,0,15)
AfficherTableau(T)

-
Edité par Ravier2000 9 septembre 2014 à 21:42:20

Utilise peut être les slices ? ou les compréhensions de listes ? Tu as toutes les possibilités, après, il faut savoir les exploiter.

Compréhension de liste :

[i for i, o in enumerates(liste_d_entier), if i > liste_d_entier[o] + 1 liste_d_entier[o] = i]

J'ai pas testé mais il me semble que c'est un truc dans cette vaine.

Salut,

Bon j'ai pas trop regardé ton code qui me semble un peu trop complexe pour ce qui est demandé (mais peut-être que ça le rend plus performant). En tout cas, j'ai aussi fait ce petit exercice, et je te propose ma solution.

PS: n'oublie pas qu'en programmation, il n'y a JAMAIS qu'une seule solution. Il en existe toujours plusieurs. Tu remarquera également que je n'ai utilisé aucune méthode de liste, pour coller au mieux à la réponse que tu as postée. Sinon, j'aurai par exemple remplacé la ligne 13 par liste_compteur.append([nb, 0]):

#Notre liste de nombre
liste_nb = [18,26,13,48,-3,19,7,22,-8,-36,0,12,15,17,38,45]

#Cette liste va compter combien de fois le nombre est plus grand que les autres
#Chaque élément sera sous la forme: [nombre, compteur]
liste_compteur = list()


#2 boucles pour compter la supériorité de chaque nombre

#La boucle principale ajoute à chaque tour le nombre et son compteur
for indice, nb in enumerate(liste_nb):
    liste_compteur += [[nb, 0]]

    #La boucle secondaire compare le nombre principal aux nombres secondaires
    #Si le nombre principal est supérieur, on ajoute 1 au compteur
    #On ajoute également 1 au compteur si le nombre principal est égale au
    #nombre secondaire, et que ce dernier se situe avant le nombre principal
    for indice_bis, nb_bis in enumerate(liste_nb):
        if (nb > nb_bis) or (nb == nb_bis and indice_bis < indice):
            liste_compteur[indice][1] += 1


#Le compteur sert à connaître la position du nombre dans la liste
#Il suffit juste de remplacer l'ancien nombre par celui approprié
for nb, compteur in liste_compteur:
    liste_nb[compteur] = nb

print(liste_nb)

Une autre façon de faire. Encore une fois, en utilisant les méthodes de liste, tu pourrai remplacer la ligne 24 par triee.insert(indice_bis, nb):

#Notre liste de nombre
nombres = [18,0,26,13,48,45,-3,19,7,22,19,-8,-36,0,12,15,15,17,38,45]

#La liste qui va contenir les futurs nombres triés
triee = list()


for indice, nb in enumerate(nombres):
    #Si c'est le premier nombre, on l'ajoute simplement à triee
    if indice == 0:
        triee += [nb]
    #Sinon on compare chaque nombre de la nombres aux nombres de la triee
    else:
        indice_bis = 0
        #Tant que l'indice_bis est inférieur à la taille de la liste triée
        #et que nb est supérieur aux nombres de cette liste:
        #on incrémente indice_bis
        while indice_bis < len(triee) and nb > triee[indice_bis]:
            indice_bis += 1

        #Quand les conditions ne sont plus respectées, on insère le nombre à la
        #position indice_bis

        triee = triee[:indice_bis] + [nb] + triee[indice_bis:]

print(triee)

@Ravier2000,

Oui le code est faux, à voir rien que le début (ligne 5), on voit que la fonction placer prend 4 arguments alors qu'elle n'en demande que 3

En première année on ne vous a pas apprit qu'il fallait mettre des espaces entre les opérateurs, que l'indentation devait être de 4 espaces et que les affectations multiples c'est le bien left, right, pivot = start, end, list[start] ? Ce sujet me fait penser qu'il serait utile de rappeler aux profs et aux élèves que le langage Python n'est pas le langage C. Quand je vois toutes ces parenthèses inutiles et tous ces noms avec des majuscules, j'en pleure de désespoir !

Concernant l'algo, je veux bien admettre que l'exercice peut avoir un intérêt pour se faire la main avec les indices des listes (ou tout autre objet indexables) et la récursivité, mais pourquoi utiliser plusieurs fonctions pour un simple quicksort !? Ça complique le code et après plus personne n'y comprend rien...

Une seule fonction suffit largement, même avec l’algorithme de base pensé pour le langage C :

def qsort(list, start=0, end=None):
    if end is None:
        end = len(list)-1
    if start < end:
        left, right, pivot = start, end, list[start]
        while True:
            while list[right] > pivot:
                right -= 1
            while list[left] < pivot:
                left += 1
            if left < right:
                list[left], list[right] = list[right], list[left]
                left, right = left+1, right-1
            else:
                break
        qsort(list, start, right)
        qsort(list, right+1, end)

Si on doit parler de performance, cet algo est complètement à la traîne en terme de vitesse d’exécution. Mais au moins c'est suffisamment clair et concis pour un cours de DUT (enfin j'espère).

Après ça on peut parler des listes de Python et de l'intérêt des langages haut niveau en démontrant qu'au prix d'une grande consommation de mémoire on peut trouver un algorithme plus simple et plus rapide :

def qsort(list):
    if len(list) > 1:
        smaller, equal, greater, pivot = [], [], [], list[0]
        for value in list:
            if value < pivot:
                smaller.append(value)
            elif value > pivot:
                greater.append(value)
            else:
                equal.append(value)
        return qsort(smaller) + equal + qsort(greater)
    return list

Et une fois que l'on s'est bien amusé avec le langage, on commence comprendre qu'être pythonic, c'est avant tout être une grosse feignasse : list.sort() !