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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| procédure tri_rapide(Liste liste)
si liste vide retourner fin si
Element* l0 // Maillon avant pivot
Element* l01 // Maillon avant l1
Element* l1
Element* fin
Element* pivot
Pile pile
Intervalle intervalle
// Intervalle(début, fin.suivant, précédent de début)
pile.empiler( Intervalle(liste, NULL, NULL) )
faire
intervalle = pile.depiler()
pivot <- intervalle.debut
l0 <- NULL
l01 <- pivot
l1 <- pivot.suivant
fin <- intervalle.fin
tant que l1 non NULL et l1 != fin faire
si pivot.mot après l1.mot faire
l01.suivant <- l1.suivant
si l0 non vide faire
l0.suivant <- l1
sinon
si intervalle.precedent non NULL
intervalle.precedent.suivant <- l1
sinon
liste <- l1
fin si
fin si
l1.suivant <- pivot
l0 <- l1
l1 <- l01.suivant
sinon
l1 <- l01
l1 <- l1.suivant
fin si
fin tant que
si l0 non NULL et intervalle.debut != l0 vide faire
si intervalle.debut.suivant != l0 faire
pile.empiler( Intervalle(intervalle.debut, pivot, intervalle.precedent) )
sinon
tester_echanger_mot(l0, intervalle.debut)
fin si
fin si
si pivot != fin faire
si pivot.suivant != fin faire
pile.empiler( Intervalle(pivot.suivant, fin, pivot) )
sinon
tester_echanger_mot(pivot.suivant, fin)
fin si
fin si
tant que pile non vide
fin procédure |
Partager