Bonjour.
Le 23 d=E9cembre, j'avais demand=E9 de l'aide pour le tri des=20
tableaux "abstraits". L'arborescence du message du 23=20
=E9tant assez d=E9velopp=E9e, je crois pr=E9f=E9rable de planter une=20
nouvelle souche.
La fonction WordBasic.SortArray, tout d'abord (sur=20
laquelle Geo m'a aid=E9 =E0 trouver la documentation; je=20
n'avais pas pens=E9 =E0 interroger le moteur de recherche,=20
tout simplement...) : je l'ai essay=E9e, elle me semble=20
avoir une rapidit=E9 d'ex=E9cution tr=E8s convenable, mais si je=20
comprends bien, elle tronque les cha=EEnes =E0 255 caract=E8res,=20
ce qui m'emp=EAche de l'utiliser, =E0 moins que quelqu'un ne=20
me passe un tuyau...
En second lieu, la version du quicksort que Pascal=20
Engelmajer a mise en ligne. Elle me semble extr=EAmement=20
rapide, nettement plus que celle que j'ai trouv=E9e dans un=20
livre d'algorithmes. Donc encore un cordial merci =E0 Pascal=20
Engelmajer.
J'avoue que j'ai eu de la peine =E0 d=E9montrer cette version.
Au cas o=F9 cela int=E9resse quelqu'un, voici une r=E9daction=20
d=E9montr=E9e.
Option Explicit
Type couple 'type des =E9l=E9ments de la pile du quicksort
mini As Long
maxi As Long
End Type
Sub MAIN()
Const TAILLE As Long =3D 4
Dim t(1 To TAILLE) As Long
Dim i As Long
' Construit un tableau o=F9, =E0 chaque =E9tape d'une partition
' (autour de l'indice m=E9dian), la valeur m=E9diane est
' la plus grande possible. C'est le plus mauvais cas pour
' cette version du quicksort.
'If TAILLE Mod 2 =3D 0 Then
' For i =3D 1 To TAILLE \ 2
' t(i) =3D 2 * i
' Next i
' For i =3D (TAILLE \ 2) + 1 To TAILLE
' t(i) =3D partieImpaire(i - 1)
' Next i
'Else ' Cas o=F9 TAILLE est impair.
' For i =3D 1 To TAILLE \ 2
' t(i) =3D 2 * i
' Next i
' t((TAILLE + 1) \ 2) =3D TAILLE
' For i =3D (TAILLE + 3) \ 2 To TAILLE
' t(i) =3D partieImpaire(i - 1)
' Next i
'End If
Call quicksort(t)
End Sub
Sub quicksort(ByRef t() As Long)
Dim tMoyen As Long
Dim iPile As Long
Dim mini As Long
Dim maxi As Long
Dim moyen As Long
Dim borne1 As Long
Dim borne2 As Long
Dim tt As Long
Dim i As Long
Dim tailleTableau As Long
Dim pile() As couple
=20
tailleTableau =3D UBound(t) + 1 - LBound(t)
ReDim pile(1 To tailleTableau)
'' La taille de la pile peut =EAtre nettement moindre
'' (de l'ordre de log(tailleTableau). Voir Sedgewick.
iPile =3D 1
pile(iPile).mini =3D 1 'Premier indice du tableau
pile(iPile).maxi =3D UBound(t) 'Dernier indice du tableau
iPile =3D iPile + 1 ' pour que iPile, =E0 la premi=E8re=20
it=E9ration du do,
'' soit =E9gal =E0 1
Do
iPile =3D iPile - 1 'la pile diminue et le programme
'' trie r=E9cursivementles parties non tri=E9es
mini =3D pile(iPile).mini ' au d=E9part 1
maxi =3D pile(iPile).maxi ' au d=E9part =E0 la dimension=20
du tableau
Do
borne1 =3D mini
borne2 =3D maxi
moyen =3D (mini + maxi) \ 2 'recuperer la valeur=20
au milieu du tableau
tMoyen =3D t(moyen)
Do
'' Invariants de cette boucle :
'' borne1 <=3D borne2 (vrai lors de la premi=E8re ex=E9cution et=20
exig=E9 par la clause de la boucle les fois suivantes) (1)
'' Pour tout i (>=3D mini et) < borne1, t(i) <=3D tMoyen. (2)
'' (Lors de la premi=E8re ex=E9cution de la boucle, borne1=20
=E9gale mini, donc c'est banal dans ce cas.)
'' Pour tout i (<=3D maxi et) > borne2, t(i) <=3D tMoyen. (3)
'' (Lors de la premi=E8re ex=E9cution de la boucle, borne2=20
=E9gale maxi, donc c'est banal dans ce cas.)
'' Il existe un i (<=3D maxi et) >=3D borne1 tel que t(i) >=3D=20
tMoyen. (4)
'' (A la premi=E8re ex=E9cution de cette boucle, c'est vrai=20
avec i =3D moyen.)
'' Il existe un i (>=3D mini et) <=3D borne2 tel que t(i) >=3D=20
tMoyen. (5)
'' (A la premi=E8re ex=E9cution de cette boucle, c'est vrai=20
avec i =3D moyen.)
Do While t(borne1) < tMoyen 'recherche=20
d 'un element plus grand
borne1 =3D borne1 + 1
Loop
'' Dans la boucle qui pr=E9c=E8de, l'usage de < et non de <=3D
'' dans "While t(borne1) < tMoyen"
'' garantit que borne1 ne montera pas plus haut que le i=20
consid=E9r=E9 en (4).
'' Cette garantie permet de ne mettre qu'une v=E9rification=20
dans la clause
'' de la boucle en question
'' et cette v=E9rification est une comparaison entre deux=20
valeurs
'' dont l'une est fixe : cela est
'' favorable =E0 la rapidit=E9 de l'ex=E9cution.
'' Maintenant, t(borne1) >=3D tMoyen.
'' Vu la condition sous laquelle borne1 a =E9t=E9 incr=E9ment=E9,
'' (2) est encore vraie, =E0 savoir :
'' Pour tout i (>=3D mini et) < borne1, t(i) <=3D tMoyen. (6)
Do While t(borne2) > tMoyen 'recherche=20
d 'un element
'' plus petit
borne2 =3D borne2 - 1
Loop
=20
'' Dans la boucle qui pr=E9c=E8de, l'usage de > et non de >=3D=20
dans "While t(borne2) > tMoyen"
'' garantit que borne2 ne descendra pas plus bas que le i=20
consid=E9r=E9 en (5).
'' Cette garantie permet de ne mettre qu'une v=E9rification=20
dans la clause de la boucle en question
'' et cette v=E9rification est une comparaison entre deux=20
valeurs dont l'une est fixe : cela est
'' favorable =E0 la rapidit=E9 de l'ex=E9cution.
'' Maintenant, t(borne2) <=3D tMoyen.
'' Vu la condition sous laquelle borne2 a =E9t=E9 d=E9cr=E9ment=E9,
'' (3) est encore vraie, =E0 savoir :
'' Pour tout i (<=3D maxi et) > borne2, t(i) <=3D tMoyen. (7)
'' En raison de (6), borne2 ne peut pas =EAtre descendu plus=20
bas
'' que borne1 - 1. Donc :
'' borne2 >=3D borne1 - 1. (8)
'' Pour les besoins du commentaire (et non du programme),=20
d=E9signons
'' respectivement par borne1bis et borne2bis
'' les valeurs actuelles de borne1 et de borne2.
'' Il r=E9sulte de (6) et (7) que :
'' si borne1bis et borne2bis sont =E9gales, t(borne1bis) =3D t
(borne2bis) =3D tMoyen. (9)
If borne1 <=3D borne2 Then
'si les deux pointeurs ne se=20
rencontrent pas
'permutation des elements design=E9s par=20
les pointeurs
tt =3D t(borne1)
t(borne1) =3D t(borne2)
t(borne2) =3D tt
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'''''''''''''''''
borne1 =3D borne1 + 1
borne2 =3D borne2 - 1
End If
=20
'' Les relations (6) et (7) sont encore vraies.
'' Dans le cas o=F9 borne1bis et borne2bis =E9taient =E9gales,=20
on a maintenant
'' borne1 =3D borne2 + 2 et t(borne1 + 1) =3D tMoyen. (10)
'' Dans le cas o=F9 borne2bis =E9tait =E9gal =E0 borne1bis - 1, le=20
If qui pr=E9c=E8de
'' ne s'est pas ex=E9cut=E9, donc
'' borne2 =3D borne1 - 1. (11)
'' Dans le cas o=F9 borne2bis =E9tait =E9gal =E0 borne1bis + 1, on=20
a maintenant
'' borne2 =3D borne1 - 1. (12)
'' Dans les autres cas, borne2bis =E9tait >=3D borne1bis + 2,=20
donc borne2 >=3D borne1; dans ce cas,
'' le If qui pr=E9c=E8de s'est ex=E9cut=E9; la permutation a rendu=20
t(borne1bis) <=3D tMoyen et la d=E9cr=E9mentation
'' a rendu borne2 =E9gal =E0 borne2bis - 1, qui est >=20
borne1bis, donc (5) est encore vraie; de m=EAme,
'' la permutation a rendu t(borne2bis) >=3D tMoyen et=20
l'incr=E9mentation a rendu borne1 =E9gal =E0 borne1bis + 1,
'' qui est < borne2bis, donc (4) est encore vraie. (13)
'' Il r=E9sulte des relations (10) =E0 (13) que si borne1 <=3D=20
borne2 (ce qui est la condition de r=E9p=E9tition de la=20
boucle),
'' les relation (4) et (5) sont encore vraies. Comme on a=20
vu que (6) et (7) sont encore vraies, les
'' invariants de boucle sont d=E9montr=E9s.
=20
=20
Loop While borne1 <=3D borne2 'si les pointeurs=20
se chevauchent,
'arr=EAt de la boucle
'' Si, au cours d'une ex=E9cution de la boucle qui pr=E9c=E8de,=20
borne1bis >=3D borne2bis - 1, la boucle ne se r=E9ex=E9cute pas;
'' dans le cas contraire, borne1 est incr=E9ment=E9, borne2=20
est d=E9cr=E9ment=E9 et la relation borne1 <=3D borne2 est
'' conserv=E9e. Comme ceci n'est pas possible ind=E9finiment,=20
la boucle s'arr=EAtera.
'' Alors borne1 > borne2 et une des conditions (10), (11),=20
(12) doit =EAtre satisfaite.
'' On en tire que tout =E9l=E9ment du sous-tableau d=E9limit=E9=20
par [mini, borne2] est <=3D =E0 tout =E9l=E9ment du sous-tableau
'' d=E9limit=E9 par [borne1, maxi], qu'il y a au plus 1=20
=E9l=E9ment entre ces deux sous-tableaux et que si cet =E9l=E9ment
'' existe, sa valeur est tMoyen, qui est >=3D =E0 tout =E9l=E9ment=20
du sous-tableau gauche et <=3D =E0 tout =E9l=E9ment du
'' sous-tableau droit. Il suffit donc de trier les deux=20
sous-tableaux en question.
If borne2 - mini < maxi - borne1 Then
'stockage dans la pile de la partie de=20
tableau non tri=E9e
'on pourrait utiliser un appel r=E9cursif de=20
quicksort en
'rempla=E7ant
'la proc=E9dure quicksort par une fonction
'quicksort(borneInf, borneSup) et =E9viter=20
ainsi la gestion de
'la pile et de la r=E9cursivit=E9
'=E7a enl=E8verait du piment au programme
If borne1 < maxi Then
pile(iPile).mini =3D borne1
pile(iPile).maxi =3D maxi
iPile =3D iPile + 1 'la pile augmente
End If
maxi =3D borne2
Else
If mini < borne2 Then
pile(iPile).mini =3D mini
pile(iPile).maxi =3D borne2
iPile =3D iPile + 1 'la pile augmente
End If
mini =3D borne1
End If
Loop While mini < maxi
Loop While iPile <> 1
End Sub
Function partieImpaire(n As Long)
Dim nCopie As Long
nCopie =3D n
Do While nCopie Mod 2 =3D 0
nCopie =3D nCopie \ 2
Loop
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Pascal Engelmajer
Salut Adrien, Je note la démonstration Bonne année -- Amicalement. Pascal "il n'y a pas de vent favorable pour celui qui ne sait pas ou il va." Sénèque. http://www.ilyapa.net/excel "Adrien Delcour" a écrit dans le message de news: 048f01c3d39d$c33e44b0$ Bonjour. Le 23 décembre, j'avais demandé de l'aide pour le tri des tableaux "abstraits". L'arborescence du message du 23 étant assez développée, je crois préférable de planter une nouvelle souche. La fonction WordBasic.SortArray, tout d'abord (sur laquelle Geo m'a aidé à trouver la documentation; je n'avais pas pensé à interroger le moteur de recherche, tout simplement...) : je l'ai essayée, elle me semble avoir une rapidité d'exécution très convenable, mais si je comprends bien, elle tronque les chaînes à 255 caractères, ce qui m'empêche de l'utiliser, à moins que quelqu'un ne me passe un tuyau... En second lieu, la version du quicksort que Pascal Engelmajer a mise en ligne. Elle me semble extrêmement rapide, nettement plus que celle que j'ai trouvée dans un livre d'algorithmes. Donc encore un cordial merci à Pascal Engelmajer. J'avoue que j'ai eu de la peine à démontrer cette version. Au cas où cela intéresse quelqu'un, voici une rédaction démontrée. Option Explicit Type couple 'type des éléments de la pile du quicksort mini As Long maxi As Long End Type
Sub MAIN()
Const TAILLE As Long = 4 Dim t(1 To TAILLE) As Long Dim i As Long
' Construit un tableau où, à chaque étape d'une partition ' (autour de l'indice médian), la valeur médiane est ' la plus grande possible. C'est le plus mauvais cas pour ' cette version du quicksort.
'If TAILLE Mod 2 = 0 Then ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' For i = (TAILLE 2) + 1 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'Else ' Cas où TAILLE est impair. ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' t((TAILLE + 1) 2) = TAILLE ' For i = (TAILLE + 3) 2 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'End If
Call quicksort(t)
End Sub
Sub quicksort(ByRef t() As Long) Dim tMoyen As Long Dim iPile As Long Dim mini As Long Dim maxi As Long Dim moyen As Long Dim borne1 As Long Dim borne2 As Long Dim tt As Long Dim i As Long Dim tailleTableau As Long Dim pile() As couple
tailleTableau = UBound(t) + 1 - LBound(t) ReDim pile(1 To tailleTableau) '' La taille de la pile peut être nettement moindre '' (de l'ordre de log(tailleTableau). Voir Sedgewick. iPile = 1 pile(iPile).mini = 1 'Premier indice du tableau pile(iPile).maxi = UBound(t) 'Dernier indice du tableau iPile = iPile + 1 ' pour que iPile, à la première itération du do, '' soit égal à 1
Do iPile = iPile - 1 'la pile diminue et le programme '' trie récursivementles parties non triées mini = pile(iPile).mini ' au départ 1 maxi = pile(iPile).maxi ' au départ à la dimension du tableau Do borne1 = mini borne2 = maxi moyen = (mini + maxi) 2 'recuperer la valeur au milieu du tableau tMoyen = t(moyen) Do
'' Invariants de cette boucle : '' borne1 <= borne2 (vrai lors de la première exécution et exigé par la clause de la boucle les fois suivantes) (1) '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (2) '' (Lors de la première exécution de la boucle, borne1 égale mini, donc c'est banal dans ce cas.) '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (3) '' (Lors de la première exécution de la boucle, borne2 égale maxi, donc c'est banal dans ce cas.) '' Il existe un i (<= maxi et) >= borne1 tel que t(i) > tMoyen. (4) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.) '' Il existe un i (>= mini et) <= borne2 tel que t(i) > tMoyen. (5) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.)
Do While t(borne1) < tMoyen 'recherche d 'un element plus grand borne1 = borne1 + 1 Loop
'' Dans la boucle qui précède, l'usage de < et non de < '' dans "While t(borne1) < tMoyen" '' garantit que borne1 ne montera pas plus haut que le i considéré en (4). '' Cette garantie permet de ne mettre qu'une vérification dans la clause '' de la boucle en question '' et cette vérification est une comparaison entre deux valeurs '' dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne1) >= tMoyen. '' Vu la condition sous laquelle borne1 a été incrémenté, '' (2) est encore vraie, à savoir : '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (6)
Do While t(borne2) > tMoyen 'recherche d 'un element '' plus petit borne2 = borne2 - 1 Loop
'' Dans la boucle qui précède, l'usage de > et non de > dans "While t(borne2) > tMoyen" '' garantit que borne2 ne descendra pas plus bas que le i considéré en (5). '' Cette garantie permet de ne mettre qu'une vérification dans la clause de la boucle en question '' et cette vérification est une comparaison entre deux valeurs dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne2) <= tMoyen. '' Vu la condition sous laquelle borne2 a été décrémenté, '' (3) est encore vraie, à savoir : '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (7) '' En raison de (6), borne2 ne peut pas être descendu plus bas '' que borne1 - 1. Donc : '' borne2 >= borne1 - 1. (8) '' Pour les besoins du commentaire (et non du programme), désignons '' respectivement par borne1bis et borne2bis '' les valeurs actuelles de borne1 et de borne2. '' Il résulte de (6) et (7) que : '' si borne1bis et borne2bis sont égales, t(borne1bis) = t (borne2bis) = tMoyen. (9) If borne1 <= borne2 Then 'si les deux pointeurs ne se rencontrent pas 'permutation des elements designés par les pointeurs tt = t(borne1) t(borne1) = t(borne2) t(borne2) = tt ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ''''''''''''''''' borne1 = borne1 + 1 borne2 = borne2 - 1
End If
'' Les relations (6) et (7) sont encore vraies. '' Dans le cas où borne1bis et borne2bis étaient égales, on a maintenant '' borne1 = borne2 + 2 et t(borne1 + 1) = tMoyen. (10) '' Dans le cas où borne2bis était égal à borne1bis - 1, le If qui précède '' ne s'est pas exécuté, donc '' borne2 = borne1 - 1. (11) '' Dans le cas où borne2bis était égal à borne1bis + 1, on a maintenant '' borne2 = borne1 - 1. (12) '' Dans les autres cas, borne2bis était >= borne1bis + 2, donc borne2 >= borne1; dans ce cas, '' le If qui précède s'est exécuté; la permutation a rendu t(borne1bis) <= tMoyen et la décrémentation '' a rendu borne2 égal à borne2bis - 1, qui est > borne1bis, donc (5) est encore vraie; de même, '' la permutation a rendu t(borne2bis) >= tMoyen et l'incrémentation a rendu borne1 égal à borne1bis + 1, '' qui est < borne2bis, donc (4) est encore vraie. (13) '' Il résulte des relations (10) à (13) que si borne1 < borne2 (ce qui est la condition de répétition de la boucle), '' les relation (4) et (5) sont encore vraies. Comme on a vu que (6) et (7) sont encore vraies, les '' invariants de boucle sont démontrés.
Loop While borne1 <= borne2 'si les pointeurs se chevauchent, 'arrêt de la boucle '' Si, au cours d'une exécution de la boucle qui précède, borne1bis >= borne2bis - 1, la boucle ne se réexécute pas; '' dans le cas contraire, borne1 est incrémenté, borne2 est décrémenté et la relation borne1 <= borne2 est '' conservée. Comme ceci n'est pas possible indéfiniment, la boucle s'arrêtera. '' Alors borne1 > borne2 et une des conditions (10), (11), (12) doit être satisfaite. '' On en tire que tout élément du sous-tableau délimité par [mini, borne2] est <= à tout élément du sous-tableau '' délimité par [borne1, maxi], qu'il y a au plus 1 élément entre ces deux sous-tableaux et que si cet élément '' existe, sa valeur est tMoyen, qui est >= à tout élément du sous-tableau gauche et <= à tout élément du '' sous-tableau droit. Il suffit donc de trier les deux sous-tableaux en question.
If borne2 - mini < maxi - borne1 Then 'stockage dans la pile de la partie de tableau non triée 'on pourrait utiliser un appel récursif de quicksort en 'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de 'la pile et de la récursivité 'ça enlèverait du piment au programme If borne1 < maxi Then pile(iPile).mini = borne1 pile(iPile).maxi = maxi iPile = iPile + 1 'la pile augmente End If maxi = borne2 Else If mini < borne2 Then pile(iPile).mini = mini pile(iPile).maxi = borne2 iPile = iPile + 1 'la pile augmente End If mini = borne1 End If Loop While mini < maxi Loop While iPile <> 1 End Sub
Function partieImpaire(n As Long)
Dim nCopie As Long nCopie = n
Do While nCopie Mod 2 = 0 nCopie = nCopie 2 Loop
partieImpaire = nCopie
End Function
' Encore merci. ' Adrien
Salut Adrien,
Je note la démonstration
Bonne année
--
Amicalement.
Pascal
"il n'y a pas de vent favorable pour celui qui ne sait pas ou il va."
Sénèque.
http://www.ilyapa.net/excel
"Adrien Delcour" <anonymous@discussions.microsoft.com> a écrit dans le
message de news: 048f01c3d39d$c33e44b0$a001280a@phx.gbl...
Bonjour.
Le 23 décembre, j'avais demandé de l'aide pour le tri des
tableaux "abstraits". L'arborescence du message du 23
étant assez développée, je crois préférable de planter une
nouvelle souche.
La fonction WordBasic.SortArray, tout d'abord (sur
laquelle Geo m'a aidé à trouver la documentation; je
n'avais pas pensé à interroger le moteur de recherche,
tout simplement...) : je l'ai essayée, elle me semble
avoir une rapidité d'exécution très convenable, mais si je
comprends bien, elle tronque les chaînes à 255 caractères,
ce qui m'empêche de l'utiliser, à moins que quelqu'un ne
me passe un tuyau...
En second lieu, la version du quicksort que Pascal
Engelmajer a mise en ligne. Elle me semble extrêmement
rapide, nettement plus que celle que j'ai trouvée dans un
livre d'algorithmes. Donc encore un cordial merci à Pascal
Engelmajer.
J'avoue que j'ai eu de la peine à démontrer cette version.
Au cas où cela intéresse quelqu'un, voici une rédaction
démontrée.
Option Explicit
Type couple 'type des éléments de la pile du quicksort
mini As Long
maxi As Long
End Type
Sub MAIN()
Const TAILLE As Long = 4
Dim t(1 To TAILLE) As Long
Dim i As Long
' Construit un tableau où, à chaque étape d'une partition
' (autour de l'indice médian), la valeur médiane est
' la plus grande possible. C'est le plus mauvais cas pour
' cette version du quicksort.
'If TAILLE Mod 2 = 0 Then
' For i = 1 To TAILLE 2
' t(i) = 2 * i
' Next i
' For i = (TAILLE 2) + 1 To TAILLE
' t(i) = partieImpaire(i - 1)
' Next i
'Else ' Cas où TAILLE est impair.
' For i = 1 To TAILLE 2
' t(i) = 2 * i
' Next i
' t((TAILLE + 1) 2) = TAILLE
' For i = (TAILLE + 3) 2 To TAILLE
' t(i) = partieImpaire(i - 1)
' Next i
'End If
Call quicksort(t)
End Sub
Sub quicksort(ByRef t() As Long)
Dim tMoyen As Long
Dim iPile As Long
Dim mini As Long
Dim maxi As Long
Dim moyen As Long
Dim borne1 As Long
Dim borne2 As Long
Dim tt As Long
Dim i As Long
Dim tailleTableau As Long
Dim pile() As couple
tailleTableau = UBound(t) + 1 - LBound(t)
ReDim pile(1 To tailleTableau)
'' La taille de la pile peut être nettement moindre
'' (de l'ordre de log(tailleTableau). Voir Sedgewick.
iPile = 1
pile(iPile).mini = 1 'Premier indice du tableau
pile(iPile).maxi = UBound(t) 'Dernier indice du tableau
iPile = iPile + 1 ' pour que iPile, à la première
itération du do,
'' soit égal à 1
Do
iPile = iPile - 1 'la pile diminue et le programme
'' trie récursivementles parties non triées
mini = pile(iPile).mini ' au départ 1
maxi = pile(iPile).maxi ' au départ à la dimension
du tableau
Do
borne1 = mini
borne2 = maxi
moyen = (mini + maxi) 2 'recuperer la valeur
au milieu du tableau
tMoyen = t(moyen)
Do
'' Invariants de cette boucle :
'' borne1 <= borne2 (vrai lors de la première exécution et
exigé par la clause de la boucle les fois suivantes) (1)
'' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (2)
'' (Lors de la première exécution de la boucle, borne1
égale mini, donc c'est banal dans ce cas.)
'' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (3)
'' (Lors de la première exécution de la boucle, borne2
égale maxi, donc c'est banal dans ce cas.)
'' Il existe un i (<= maxi et) >= borne1 tel que t(i) > tMoyen. (4)
'' (A la première exécution de cette boucle, c'est vrai
avec i = moyen.)
'' Il existe un i (>= mini et) <= borne2 tel que t(i) > tMoyen. (5)
'' (A la première exécution de cette boucle, c'est vrai
avec i = moyen.)
Do While t(borne1) < tMoyen 'recherche
d 'un element plus grand
borne1 = borne1 + 1
Loop
'' Dans la boucle qui précède, l'usage de < et non de < '' dans "While t(borne1) < tMoyen"
'' garantit que borne1 ne montera pas plus haut que le i
considéré en (4).
'' Cette garantie permet de ne mettre qu'une vérification
dans la clause
'' de la boucle en question
'' et cette vérification est une comparaison entre deux
valeurs
'' dont l'une est fixe : cela est
'' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne1) >= tMoyen.
'' Vu la condition sous laquelle borne1 a été incrémenté,
'' (2) est encore vraie, à savoir :
'' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (6)
Do While t(borne2) > tMoyen 'recherche
d 'un element
'' plus petit
borne2 = borne2 - 1
Loop
'' Dans la boucle qui précède, l'usage de > et non de > dans "While t(borne2) > tMoyen"
'' garantit que borne2 ne descendra pas plus bas que le i
considéré en (5).
'' Cette garantie permet de ne mettre qu'une vérification
dans la clause de la boucle en question
'' et cette vérification est une comparaison entre deux
valeurs dont l'une est fixe : cela est
'' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne2) <= tMoyen.
'' Vu la condition sous laquelle borne2 a été décrémenté,
'' (3) est encore vraie, à savoir :
'' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (7)
'' En raison de (6), borne2 ne peut pas être descendu plus
bas
'' que borne1 - 1. Donc :
'' borne2 >= borne1 - 1. (8)
'' Pour les besoins du commentaire (et non du programme),
désignons
'' respectivement par borne1bis et borne2bis
'' les valeurs actuelles de borne1 et de borne2.
'' Il résulte de (6) et (7) que :
'' si borne1bis et borne2bis sont égales, t(borne1bis) = t
(borne2bis) = tMoyen. (9)
If borne1 <= borne2 Then
'si les deux pointeurs ne se
rencontrent pas
'permutation des elements designés par
les pointeurs
tt = t(borne1)
t(borne1) = t(borne2)
t(borne2) = tt
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'''''''''''''''''
borne1 = borne1 + 1
borne2 = borne2 - 1
End If
'' Les relations (6) et (7) sont encore vraies.
'' Dans le cas où borne1bis et borne2bis étaient égales,
on a maintenant
'' borne1 = borne2 + 2 et t(borne1 + 1) = tMoyen. (10)
'' Dans le cas où borne2bis était égal à borne1bis - 1, le
If qui précède
'' ne s'est pas exécuté, donc
'' borne2 = borne1 - 1. (11)
'' Dans le cas où borne2bis était égal à borne1bis + 1, on
a maintenant
'' borne2 = borne1 - 1. (12)
'' Dans les autres cas, borne2bis était >= borne1bis + 2,
donc borne2 >= borne1; dans ce cas,
'' le If qui précède s'est exécuté; la permutation a rendu
t(borne1bis) <= tMoyen et la décrémentation
'' a rendu borne2 égal à borne2bis - 1, qui est >
borne1bis, donc (5) est encore vraie; de même,
'' la permutation a rendu t(borne2bis) >= tMoyen et
l'incrémentation a rendu borne1 égal à borne1bis + 1,
'' qui est < borne2bis, donc (4) est encore vraie. (13)
'' Il résulte des relations (10) à (13) que si borne1 < borne2 (ce qui est la condition de répétition de la
boucle),
'' les relation (4) et (5) sont encore vraies. Comme on a
vu que (6) et (7) sont encore vraies, les
'' invariants de boucle sont démontrés.
Loop While borne1 <= borne2 'si les pointeurs
se chevauchent,
'arrêt de la boucle
'' Si, au cours d'une exécution de la boucle qui précède,
borne1bis >= borne2bis - 1, la boucle ne se réexécute pas;
'' dans le cas contraire, borne1 est incrémenté, borne2
est décrémenté et la relation borne1 <= borne2 est
'' conservée. Comme ceci n'est pas possible indéfiniment,
la boucle s'arrêtera.
'' Alors borne1 > borne2 et une des conditions (10), (11),
(12) doit être satisfaite.
'' On en tire que tout élément du sous-tableau délimité
par [mini, borne2] est <= à tout élément du sous-tableau
'' délimité par [borne1, maxi], qu'il y a au plus 1
élément entre ces deux sous-tableaux et que si cet élément
'' existe, sa valeur est tMoyen, qui est >= à tout élément
du sous-tableau gauche et <= à tout élément du
'' sous-tableau droit. Il suffit donc de trier les deux
sous-tableaux en question.
If borne2 - mini < maxi - borne1 Then
'stockage dans la pile de la partie de
tableau non triée
'on pourrait utiliser un appel récursif de
quicksort en
'remplaçant
'la procédure quicksort par une fonction
'quicksort(borneInf, borneSup) et éviter
ainsi la gestion de
'la pile et de la récursivité
'ça enlèverait du piment au programme
If borne1 < maxi Then
pile(iPile).mini = borne1
pile(iPile).maxi = maxi
iPile = iPile + 1 'la pile augmente
End If
maxi = borne2
Else
If mini < borne2 Then
pile(iPile).mini = mini
pile(iPile).maxi = borne2
iPile = iPile + 1 'la pile augmente
End If
mini = borne1
End If
Loop While mini < maxi
Loop While iPile <> 1
End Sub
Salut Adrien, Je note la démonstration Bonne année -- Amicalement. Pascal "il n'y a pas de vent favorable pour celui qui ne sait pas ou il va." Sénèque. http://www.ilyapa.net/excel "Adrien Delcour" a écrit dans le message de news: 048f01c3d39d$c33e44b0$ Bonjour. Le 23 décembre, j'avais demandé de l'aide pour le tri des tableaux "abstraits". L'arborescence du message du 23 étant assez développée, je crois préférable de planter une nouvelle souche. La fonction WordBasic.SortArray, tout d'abord (sur laquelle Geo m'a aidé à trouver la documentation; je n'avais pas pensé à interroger le moteur de recherche, tout simplement...) : je l'ai essayée, elle me semble avoir une rapidité d'exécution très convenable, mais si je comprends bien, elle tronque les chaînes à 255 caractères, ce qui m'empêche de l'utiliser, à moins que quelqu'un ne me passe un tuyau... En second lieu, la version du quicksort que Pascal Engelmajer a mise en ligne. Elle me semble extrêmement rapide, nettement plus que celle que j'ai trouvée dans un livre d'algorithmes. Donc encore un cordial merci à Pascal Engelmajer. J'avoue que j'ai eu de la peine à démontrer cette version. Au cas où cela intéresse quelqu'un, voici une rédaction démontrée. Option Explicit Type couple 'type des éléments de la pile du quicksort mini As Long maxi As Long End Type
Sub MAIN()
Const TAILLE As Long = 4 Dim t(1 To TAILLE) As Long Dim i As Long
' Construit un tableau où, à chaque étape d'une partition ' (autour de l'indice médian), la valeur médiane est ' la plus grande possible. C'est le plus mauvais cas pour ' cette version du quicksort.
'If TAILLE Mod 2 = 0 Then ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' For i = (TAILLE 2) + 1 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'Else ' Cas où TAILLE est impair. ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' t((TAILLE + 1) 2) = TAILLE ' For i = (TAILLE + 3) 2 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'End If
Call quicksort(t)
End Sub
Sub quicksort(ByRef t() As Long) Dim tMoyen As Long Dim iPile As Long Dim mini As Long Dim maxi As Long Dim moyen As Long Dim borne1 As Long Dim borne2 As Long Dim tt As Long Dim i As Long Dim tailleTableau As Long Dim pile() As couple
tailleTableau = UBound(t) + 1 - LBound(t) ReDim pile(1 To tailleTableau) '' La taille de la pile peut être nettement moindre '' (de l'ordre de log(tailleTableau). Voir Sedgewick. iPile = 1 pile(iPile).mini = 1 'Premier indice du tableau pile(iPile).maxi = UBound(t) 'Dernier indice du tableau iPile = iPile + 1 ' pour que iPile, à la première itération du do, '' soit égal à 1
Do iPile = iPile - 1 'la pile diminue et le programme '' trie récursivementles parties non triées mini = pile(iPile).mini ' au départ 1 maxi = pile(iPile).maxi ' au départ à la dimension du tableau Do borne1 = mini borne2 = maxi moyen = (mini + maxi) 2 'recuperer la valeur au milieu du tableau tMoyen = t(moyen) Do
'' Invariants de cette boucle : '' borne1 <= borne2 (vrai lors de la première exécution et exigé par la clause de la boucle les fois suivantes) (1) '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (2) '' (Lors de la première exécution de la boucle, borne1 égale mini, donc c'est banal dans ce cas.) '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (3) '' (Lors de la première exécution de la boucle, borne2 égale maxi, donc c'est banal dans ce cas.) '' Il existe un i (<= maxi et) >= borne1 tel que t(i) > tMoyen. (4) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.) '' Il existe un i (>= mini et) <= borne2 tel que t(i) > tMoyen. (5) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.)
Do While t(borne1) < tMoyen 'recherche d 'un element plus grand borne1 = borne1 + 1 Loop
'' Dans la boucle qui précède, l'usage de < et non de < '' dans "While t(borne1) < tMoyen" '' garantit que borne1 ne montera pas plus haut que le i considéré en (4). '' Cette garantie permet de ne mettre qu'une vérification dans la clause '' de la boucle en question '' et cette vérification est une comparaison entre deux valeurs '' dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne1) >= tMoyen. '' Vu la condition sous laquelle borne1 a été incrémenté, '' (2) est encore vraie, à savoir : '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (6)
Do While t(borne2) > tMoyen 'recherche d 'un element '' plus petit borne2 = borne2 - 1 Loop
'' Dans la boucle qui précède, l'usage de > et non de > dans "While t(borne2) > tMoyen" '' garantit que borne2 ne descendra pas plus bas que le i considéré en (5). '' Cette garantie permet de ne mettre qu'une vérification dans la clause de la boucle en question '' et cette vérification est une comparaison entre deux valeurs dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne2) <= tMoyen. '' Vu la condition sous laquelle borne2 a été décrémenté, '' (3) est encore vraie, à savoir : '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (7) '' En raison de (6), borne2 ne peut pas être descendu plus bas '' que borne1 - 1. Donc : '' borne2 >= borne1 - 1. (8) '' Pour les besoins du commentaire (et non du programme), désignons '' respectivement par borne1bis et borne2bis '' les valeurs actuelles de borne1 et de borne2. '' Il résulte de (6) et (7) que : '' si borne1bis et borne2bis sont égales, t(borne1bis) = t (borne2bis) = tMoyen. (9) If borne1 <= borne2 Then 'si les deux pointeurs ne se rencontrent pas 'permutation des elements designés par les pointeurs tt = t(borne1) t(borne1) = t(borne2) t(borne2) = tt ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ''''''''''''''''' borne1 = borne1 + 1 borne2 = borne2 - 1
End If
'' Les relations (6) et (7) sont encore vraies. '' Dans le cas où borne1bis et borne2bis étaient égales, on a maintenant '' borne1 = borne2 + 2 et t(borne1 + 1) = tMoyen. (10) '' Dans le cas où borne2bis était égal à borne1bis - 1, le If qui précède '' ne s'est pas exécuté, donc '' borne2 = borne1 - 1. (11) '' Dans le cas où borne2bis était égal à borne1bis + 1, on a maintenant '' borne2 = borne1 - 1. (12) '' Dans les autres cas, borne2bis était >= borne1bis + 2, donc borne2 >= borne1; dans ce cas, '' le If qui précède s'est exécuté; la permutation a rendu t(borne1bis) <= tMoyen et la décrémentation '' a rendu borne2 égal à borne2bis - 1, qui est > borne1bis, donc (5) est encore vraie; de même, '' la permutation a rendu t(borne2bis) >= tMoyen et l'incrémentation a rendu borne1 égal à borne1bis + 1, '' qui est < borne2bis, donc (4) est encore vraie. (13) '' Il résulte des relations (10) à (13) que si borne1 < borne2 (ce qui est la condition de répétition de la boucle), '' les relation (4) et (5) sont encore vraies. Comme on a vu que (6) et (7) sont encore vraies, les '' invariants de boucle sont démontrés.
Loop While borne1 <= borne2 'si les pointeurs se chevauchent, 'arrêt de la boucle '' Si, au cours d'une exécution de la boucle qui précède, borne1bis >= borne2bis - 1, la boucle ne se réexécute pas; '' dans le cas contraire, borne1 est incrémenté, borne2 est décrémenté et la relation borne1 <= borne2 est '' conservée. Comme ceci n'est pas possible indéfiniment, la boucle s'arrêtera. '' Alors borne1 > borne2 et une des conditions (10), (11), (12) doit être satisfaite. '' On en tire que tout élément du sous-tableau délimité par [mini, borne2] est <= à tout élément du sous-tableau '' délimité par [borne1, maxi], qu'il y a au plus 1 élément entre ces deux sous-tableaux et que si cet élément '' existe, sa valeur est tMoyen, qui est >= à tout élément du sous-tableau gauche et <= à tout élément du '' sous-tableau droit. Il suffit donc de trier les deux sous-tableaux en question.
If borne2 - mini < maxi - borne1 Then 'stockage dans la pile de la partie de tableau non triée 'on pourrait utiliser un appel récursif de quicksort en 'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de 'la pile et de la récursivité 'ça enlèverait du piment au programme If borne1 < maxi Then pile(iPile).mini = borne1 pile(iPile).maxi = maxi iPile = iPile + 1 'la pile augmente End If maxi = borne2 Else If mini < borne2 Then pile(iPile).mini = mini pile(iPile).maxi = borne2 iPile = iPile + 1 'la pile augmente End If mini = borne1 End If Loop While mini < maxi Loop While iPile <> 1 End Sub
Function partieImpaire(n As Long)
Dim nCopie As Long nCopie = n
Do While nCopie Mod 2 = 0 nCopie = nCopie 2 Loop
partieImpaire = nCopie
End Function
' Encore merci. ' Adrien
Pascal Engelmajer
Salut Adrien, Je relève : 'on pourrait utiliser un appel récursif de quicksort en 'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de 'la pile et de la récursivité 'ça enlèverait du piment au programme D'après mes tests, pas seulement, car la récursivité est couteuse en ressources ce qui n'est pas le cas de cette gestion à la mano de la pile...
-- Amicalement. Pascal "il n'y a pas de vent favorable pour celui qui ne sait pas ou il va." Sénèque. http://www.ilyapa.net/excel "Adrien Delcour" a écrit dans le message de news: 048f01c3d39d$c33e44b0$ Bonjour. Le 23 décembre, j'avais demandé de l'aide pour le tri des tableaux "abstraits". L'arborescence du message du 23 étant assez développée, je crois préférable de planter une nouvelle souche. La fonction WordBasic.SortArray, tout d'abord (sur laquelle Geo m'a aidé à trouver la documentation; je n'avais pas pensé à interroger le moteur de recherche, tout simplement...) : je l'ai essayée, elle me semble avoir une rapidité d'exécution très convenable, mais si je comprends bien, elle tronque les chaînes à 255 caractères, ce qui m'empêche de l'utiliser, à moins que quelqu'un ne me passe un tuyau... En second lieu, la version du quicksort que Pascal Engelmajer a mise en ligne. Elle me semble extrêmement rapide, nettement plus que celle que j'ai trouvée dans un livre d'algorithmes. Donc encore un cordial merci à Pascal Engelmajer. J'avoue que j'ai eu de la peine à démontrer cette version. Au cas où cela intéresse quelqu'un, voici une rédaction démontrée. Option Explicit Type couple 'type des éléments de la pile du quicksort mini As Long maxi As Long End Type
Sub MAIN()
Const TAILLE As Long = 4 Dim t(1 To TAILLE) As Long Dim i As Long
' Construit un tableau où, à chaque étape d'une partition ' (autour de l'indice médian), la valeur médiane est ' la plus grande possible. C'est le plus mauvais cas pour ' cette version du quicksort.
'If TAILLE Mod 2 = 0 Then ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' For i = (TAILLE 2) + 1 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'Else ' Cas où TAILLE est impair. ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' t((TAILLE + 1) 2) = TAILLE ' For i = (TAILLE + 3) 2 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'End If
Call quicksort(t)
End Sub
Sub quicksort(ByRef t() As Long) Dim tMoyen As Long Dim iPile As Long Dim mini As Long Dim maxi As Long Dim moyen As Long Dim borne1 As Long Dim borne2 As Long Dim tt As Long Dim i As Long Dim tailleTableau As Long Dim pile() As couple
tailleTableau = UBound(t) + 1 - LBound(t) ReDim pile(1 To tailleTableau) '' La taille de la pile peut être nettement moindre '' (de l'ordre de log(tailleTableau). Voir Sedgewick. iPile = 1 pile(iPile).mini = 1 'Premier indice du tableau pile(iPile).maxi = UBound(t) 'Dernier indice du tableau iPile = iPile + 1 ' pour que iPile, à la première itération du do, '' soit égal à 1
Do iPile = iPile - 1 'la pile diminue et le programme '' trie récursivementles parties non triées mini = pile(iPile).mini ' au départ 1 maxi = pile(iPile).maxi ' au départ à la dimension du tableau Do borne1 = mini borne2 = maxi moyen = (mini + maxi) 2 'recuperer la valeur au milieu du tableau tMoyen = t(moyen) Do
'' Invariants de cette boucle : '' borne1 <= borne2 (vrai lors de la première exécution et exigé par la clause de la boucle les fois suivantes) (1) '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (2) '' (Lors de la première exécution de la boucle, borne1 égale mini, donc c'est banal dans ce cas.) '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (3) '' (Lors de la première exécution de la boucle, borne2 égale maxi, donc c'est banal dans ce cas.) '' Il existe un i (<= maxi et) >= borne1 tel que t(i) > tMoyen. (4) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.) '' Il existe un i (>= mini et) <= borne2 tel que t(i) > tMoyen. (5) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.)
Do While t(borne1) < tMoyen 'recherche d 'un element plus grand borne1 = borne1 + 1 Loop
'' Dans la boucle qui précède, l'usage de < et non de < '' dans "While t(borne1) < tMoyen" '' garantit que borne1 ne montera pas plus haut que le i considéré en (4). '' Cette garantie permet de ne mettre qu'une vérification dans la clause '' de la boucle en question '' et cette vérification est une comparaison entre deux valeurs '' dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne1) >= tMoyen. '' Vu la condition sous laquelle borne1 a été incrémenté, '' (2) est encore vraie, à savoir : '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (6)
Do While t(borne2) > tMoyen 'recherche d 'un element '' plus petit borne2 = borne2 - 1 Loop
'' Dans la boucle qui précède, l'usage de > et non de > dans "While t(borne2) > tMoyen" '' garantit que borne2 ne descendra pas plus bas que le i considéré en (5). '' Cette garantie permet de ne mettre qu'une vérification dans la clause de la boucle en question '' et cette vérification est une comparaison entre deux valeurs dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne2) <= tMoyen. '' Vu la condition sous laquelle borne2 a été décrémenté, '' (3) est encore vraie, à savoir : '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (7) '' En raison de (6), borne2 ne peut pas être descendu plus bas '' que borne1 - 1. Donc : '' borne2 >= borne1 - 1. (8) '' Pour les besoins du commentaire (et non du programme), désignons '' respectivement par borne1bis et borne2bis '' les valeurs actuelles de borne1 et de borne2. '' Il résulte de (6) et (7) que : '' si borne1bis et borne2bis sont égales, t(borne1bis) = t (borne2bis) = tMoyen. (9) If borne1 <= borne2 Then 'si les deux pointeurs ne se rencontrent pas 'permutation des elements designés par les pointeurs tt = t(borne1) t(borne1) = t(borne2) t(borne2) = tt ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ''''''''''''''''' borne1 = borne1 + 1 borne2 = borne2 - 1
End If
'' Les relations (6) et (7) sont encore vraies. '' Dans le cas où borne1bis et borne2bis étaient égales, on a maintenant '' borne1 = borne2 + 2 et t(borne1 + 1) = tMoyen. (10) '' Dans le cas où borne2bis était égal à borne1bis - 1, le If qui précède '' ne s'est pas exécuté, donc '' borne2 = borne1 - 1. (11) '' Dans le cas où borne2bis était égal à borne1bis + 1, on a maintenant '' borne2 = borne1 - 1. (12) '' Dans les autres cas, borne2bis était >= borne1bis + 2, donc borne2 >= borne1; dans ce cas, '' le If qui précède s'est exécuté; la permutation a rendu t(borne1bis) <= tMoyen et la décrémentation '' a rendu borne2 égal à borne2bis - 1, qui est > borne1bis, donc (5) est encore vraie; de même, '' la permutation a rendu t(borne2bis) >= tMoyen et l'incrémentation a rendu borne1 égal à borne1bis + 1, '' qui est < borne2bis, donc (4) est encore vraie. (13) '' Il résulte des relations (10) à (13) que si borne1 < borne2 (ce qui est la condition de répétition de la boucle), '' les relation (4) et (5) sont encore vraies. Comme on a vu que (6) et (7) sont encore vraies, les '' invariants de boucle sont démontrés.
Loop While borne1 <= borne2 'si les pointeurs se chevauchent, 'arrêt de la boucle '' Si, au cours d'une exécution de la boucle qui précède, borne1bis >= borne2bis - 1, la boucle ne se réexécute pas; '' dans le cas contraire, borne1 est incrémenté, borne2 est décrémenté et la relation borne1 <= borne2 est '' conservée. Comme ceci n'est pas possible indéfiniment, la boucle s'arrêtera. '' Alors borne1 > borne2 et une des conditions (10), (11), (12) doit être satisfaite. '' On en tire que tout élément du sous-tableau délimité par [mini, borne2] est <= à tout élément du sous-tableau '' délimité par [borne1, maxi], qu'il y a au plus 1 élément entre ces deux sous-tableaux et que si cet élément '' existe, sa valeur est tMoyen, qui est >= à tout élément du sous-tableau gauche et <= à tout élément du '' sous-tableau droit. Il suffit donc de trier les deux sous-tableaux en question.
If borne2 - mini < maxi - borne1 Then 'stockage dans la pile de la partie de tableau non triée 'on pourrait utiliser un appel récursif de quicksort en 'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de 'la pile et de la récursivité 'ça enlèverait du piment au programme If borne1 < maxi Then pile(iPile).mini = borne1 pile(iPile).maxi = maxi iPile = iPile + 1 'la pile augmente End If maxi = borne2 Else If mini < borne2 Then pile(iPile).mini = mini pile(iPile).maxi = borne2 iPile = iPile + 1 'la pile augmente End If mini = borne1 End If Loop While mini < maxi Loop While iPile <> 1 End Sub
Function partieImpaire(n As Long)
Dim nCopie As Long nCopie = n
Do While nCopie Mod 2 = 0 nCopie = nCopie 2 Loop
partieImpaire = nCopie
End Function
' Encore merci. ' Adrien
Salut Adrien,
Je relève :
'on pourrait utiliser un appel récursif de quicksort en
'remplaçant
'la procédure quicksort par une fonction
'quicksort(borneInf, borneSup) et éviter ainsi la gestion de
'la pile et de la récursivité
'ça enlèverait du piment au programme
D'après mes tests, pas seulement, car la récursivité est couteuse en
ressources ce qui n'est pas le cas de cette gestion à la mano de la pile...
--
Amicalement.
Pascal
"il n'y a pas de vent favorable pour celui qui ne sait pas ou il va."
Sénèque.
http://www.ilyapa.net/excel
"Adrien Delcour" <anonymous@discussions.microsoft.com> a écrit dans le
message de news: 048f01c3d39d$c33e44b0$a001280a@phx.gbl...
Bonjour.
Le 23 décembre, j'avais demandé de l'aide pour le tri des
tableaux "abstraits". L'arborescence du message du 23
étant assez développée, je crois préférable de planter une
nouvelle souche.
La fonction WordBasic.SortArray, tout d'abord (sur
laquelle Geo m'a aidé à trouver la documentation; je
n'avais pas pensé à interroger le moteur de recherche,
tout simplement...) : je l'ai essayée, elle me semble
avoir une rapidité d'exécution très convenable, mais si je
comprends bien, elle tronque les chaînes à 255 caractères,
ce qui m'empêche de l'utiliser, à moins que quelqu'un ne
me passe un tuyau...
En second lieu, la version du quicksort que Pascal
Engelmajer a mise en ligne. Elle me semble extrêmement
rapide, nettement plus que celle que j'ai trouvée dans un
livre d'algorithmes. Donc encore un cordial merci à Pascal
Engelmajer.
J'avoue que j'ai eu de la peine à démontrer cette version.
Au cas où cela intéresse quelqu'un, voici une rédaction
démontrée.
Option Explicit
Type couple 'type des éléments de la pile du quicksort
mini As Long
maxi As Long
End Type
Sub MAIN()
Const TAILLE As Long = 4
Dim t(1 To TAILLE) As Long
Dim i As Long
' Construit un tableau où, à chaque étape d'une partition
' (autour de l'indice médian), la valeur médiane est
' la plus grande possible. C'est le plus mauvais cas pour
' cette version du quicksort.
'If TAILLE Mod 2 = 0 Then
' For i = 1 To TAILLE 2
' t(i) = 2 * i
' Next i
' For i = (TAILLE 2) + 1 To TAILLE
' t(i) = partieImpaire(i - 1)
' Next i
'Else ' Cas où TAILLE est impair.
' For i = 1 To TAILLE 2
' t(i) = 2 * i
' Next i
' t((TAILLE + 1) 2) = TAILLE
' For i = (TAILLE + 3) 2 To TAILLE
' t(i) = partieImpaire(i - 1)
' Next i
'End If
Call quicksort(t)
End Sub
Sub quicksort(ByRef t() As Long)
Dim tMoyen As Long
Dim iPile As Long
Dim mini As Long
Dim maxi As Long
Dim moyen As Long
Dim borne1 As Long
Dim borne2 As Long
Dim tt As Long
Dim i As Long
Dim tailleTableau As Long
Dim pile() As couple
tailleTableau = UBound(t) + 1 - LBound(t)
ReDim pile(1 To tailleTableau)
'' La taille de la pile peut être nettement moindre
'' (de l'ordre de log(tailleTableau). Voir Sedgewick.
iPile = 1
pile(iPile).mini = 1 'Premier indice du tableau
pile(iPile).maxi = UBound(t) 'Dernier indice du tableau
iPile = iPile + 1 ' pour que iPile, à la première
itération du do,
'' soit égal à 1
Do
iPile = iPile - 1 'la pile diminue et le programme
'' trie récursivementles parties non triées
mini = pile(iPile).mini ' au départ 1
maxi = pile(iPile).maxi ' au départ à la dimension
du tableau
Do
borne1 = mini
borne2 = maxi
moyen = (mini + maxi) 2 'recuperer la valeur
au milieu du tableau
tMoyen = t(moyen)
Do
'' Invariants de cette boucle :
'' borne1 <= borne2 (vrai lors de la première exécution et
exigé par la clause de la boucle les fois suivantes) (1)
'' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (2)
'' (Lors de la première exécution de la boucle, borne1
égale mini, donc c'est banal dans ce cas.)
'' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (3)
'' (Lors de la première exécution de la boucle, borne2
égale maxi, donc c'est banal dans ce cas.)
'' Il existe un i (<= maxi et) >= borne1 tel que t(i) > tMoyen. (4)
'' (A la première exécution de cette boucle, c'est vrai
avec i = moyen.)
'' Il existe un i (>= mini et) <= borne2 tel que t(i) > tMoyen. (5)
'' (A la première exécution de cette boucle, c'est vrai
avec i = moyen.)
Do While t(borne1) < tMoyen 'recherche
d 'un element plus grand
borne1 = borne1 + 1
Loop
'' Dans la boucle qui précède, l'usage de < et non de < '' dans "While t(borne1) < tMoyen"
'' garantit que borne1 ne montera pas plus haut que le i
considéré en (4).
'' Cette garantie permet de ne mettre qu'une vérification
dans la clause
'' de la boucle en question
'' et cette vérification est une comparaison entre deux
valeurs
'' dont l'une est fixe : cela est
'' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne1) >= tMoyen.
'' Vu la condition sous laquelle borne1 a été incrémenté,
'' (2) est encore vraie, à savoir :
'' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (6)
Do While t(borne2) > tMoyen 'recherche
d 'un element
'' plus petit
borne2 = borne2 - 1
Loop
'' Dans la boucle qui précède, l'usage de > et non de > dans "While t(borne2) > tMoyen"
'' garantit que borne2 ne descendra pas plus bas que le i
considéré en (5).
'' Cette garantie permet de ne mettre qu'une vérification
dans la clause de la boucle en question
'' et cette vérification est une comparaison entre deux
valeurs dont l'une est fixe : cela est
'' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne2) <= tMoyen.
'' Vu la condition sous laquelle borne2 a été décrémenté,
'' (3) est encore vraie, à savoir :
'' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (7)
'' En raison de (6), borne2 ne peut pas être descendu plus
bas
'' que borne1 - 1. Donc :
'' borne2 >= borne1 - 1. (8)
'' Pour les besoins du commentaire (et non du programme),
désignons
'' respectivement par borne1bis et borne2bis
'' les valeurs actuelles de borne1 et de borne2.
'' Il résulte de (6) et (7) que :
'' si borne1bis et borne2bis sont égales, t(borne1bis) = t
(borne2bis) = tMoyen. (9)
If borne1 <= borne2 Then
'si les deux pointeurs ne se
rencontrent pas
'permutation des elements designés par
les pointeurs
tt = t(borne1)
t(borne1) = t(borne2)
t(borne2) = tt
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'''''''''''''''''
borne1 = borne1 + 1
borne2 = borne2 - 1
End If
'' Les relations (6) et (7) sont encore vraies.
'' Dans le cas où borne1bis et borne2bis étaient égales,
on a maintenant
'' borne1 = borne2 + 2 et t(borne1 + 1) = tMoyen. (10)
'' Dans le cas où borne2bis était égal à borne1bis - 1, le
If qui précède
'' ne s'est pas exécuté, donc
'' borne2 = borne1 - 1. (11)
'' Dans le cas où borne2bis était égal à borne1bis + 1, on
a maintenant
'' borne2 = borne1 - 1. (12)
'' Dans les autres cas, borne2bis était >= borne1bis + 2,
donc borne2 >= borne1; dans ce cas,
'' le If qui précède s'est exécuté; la permutation a rendu
t(borne1bis) <= tMoyen et la décrémentation
'' a rendu borne2 égal à borne2bis - 1, qui est >
borne1bis, donc (5) est encore vraie; de même,
'' la permutation a rendu t(borne2bis) >= tMoyen et
l'incrémentation a rendu borne1 égal à borne1bis + 1,
'' qui est < borne2bis, donc (4) est encore vraie. (13)
'' Il résulte des relations (10) à (13) que si borne1 < borne2 (ce qui est la condition de répétition de la
boucle),
'' les relation (4) et (5) sont encore vraies. Comme on a
vu que (6) et (7) sont encore vraies, les
'' invariants de boucle sont démontrés.
Loop While borne1 <= borne2 'si les pointeurs
se chevauchent,
'arrêt de la boucle
'' Si, au cours d'une exécution de la boucle qui précède,
borne1bis >= borne2bis - 1, la boucle ne se réexécute pas;
'' dans le cas contraire, borne1 est incrémenté, borne2
est décrémenté et la relation borne1 <= borne2 est
'' conservée. Comme ceci n'est pas possible indéfiniment,
la boucle s'arrêtera.
'' Alors borne1 > borne2 et une des conditions (10), (11),
(12) doit être satisfaite.
'' On en tire que tout élément du sous-tableau délimité
par [mini, borne2] est <= à tout élément du sous-tableau
'' délimité par [borne1, maxi], qu'il y a au plus 1
élément entre ces deux sous-tableaux et que si cet élément
'' existe, sa valeur est tMoyen, qui est >= à tout élément
du sous-tableau gauche et <= à tout élément du
'' sous-tableau droit. Il suffit donc de trier les deux
sous-tableaux en question.
If borne2 - mini < maxi - borne1 Then
'stockage dans la pile de la partie de
tableau non triée
'on pourrait utiliser un appel récursif de
quicksort en
'remplaçant
'la procédure quicksort par une fonction
'quicksort(borneInf, borneSup) et éviter
ainsi la gestion de
'la pile et de la récursivité
'ça enlèverait du piment au programme
If borne1 < maxi Then
pile(iPile).mini = borne1
pile(iPile).maxi = maxi
iPile = iPile + 1 'la pile augmente
End If
maxi = borne2
Else
If mini < borne2 Then
pile(iPile).mini = mini
pile(iPile).maxi = borne2
iPile = iPile + 1 'la pile augmente
End If
mini = borne1
End If
Loop While mini < maxi
Loop While iPile <> 1
End Sub
Salut Adrien, Je relève : 'on pourrait utiliser un appel récursif de quicksort en 'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de 'la pile et de la récursivité 'ça enlèverait du piment au programme D'après mes tests, pas seulement, car la récursivité est couteuse en ressources ce qui n'est pas le cas de cette gestion à la mano de la pile...
-- Amicalement. Pascal "il n'y a pas de vent favorable pour celui qui ne sait pas ou il va." Sénèque. http://www.ilyapa.net/excel "Adrien Delcour" a écrit dans le message de news: 048f01c3d39d$c33e44b0$ Bonjour. Le 23 décembre, j'avais demandé de l'aide pour le tri des tableaux "abstraits". L'arborescence du message du 23 étant assez développée, je crois préférable de planter une nouvelle souche. La fonction WordBasic.SortArray, tout d'abord (sur laquelle Geo m'a aidé à trouver la documentation; je n'avais pas pensé à interroger le moteur de recherche, tout simplement...) : je l'ai essayée, elle me semble avoir une rapidité d'exécution très convenable, mais si je comprends bien, elle tronque les chaînes à 255 caractères, ce qui m'empêche de l'utiliser, à moins que quelqu'un ne me passe un tuyau... En second lieu, la version du quicksort que Pascal Engelmajer a mise en ligne. Elle me semble extrêmement rapide, nettement plus que celle que j'ai trouvée dans un livre d'algorithmes. Donc encore un cordial merci à Pascal Engelmajer. J'avoue que j'ai eu de la peine à démontrer cette version. Au cas où cela intéresse quelqu'un, voici une rédaction démontrée. Option Explicit Type couple 'type des éléments de la pile du quicksort mini As Long maxi As Long End Type
Sub MAIN()
Const TAILLE As Long = 4 Dim t(1 To TAILLE) As Long Dim i As Long
' Construit un tableau où, à chaque étape d'une partition ' (autour de l'indice médian), la valeur médiane est ' la plus grande possible. C'est le plus mauvais cas pour ' cette version du quicksort.
'If TAILLE Mod 2 = 0 Then ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' For i = (TAILLE 2) + 1 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'Else ' Cas où TAILLE est impair. ' For i = 1 To TAILLE 2 ' t(i) = 2 * i ' Next i ' t((TAILLE + 1) 2) = TAILLE ' For i = (TAILLE + 3) 2 To TAILLE ' t(i) = partieImpaire(i - 1) ' Next i 'End If
Call quicksort(t)
End Sub
Sub quicksort(ByRef t() As Long) Dim tMoyen As Long Dim iPile As Long Dim mini As Long Dim maxi As Long Dim moyen As Long Dim borne1 As Long Dim borne2 As Long Dim tt As Long Dim i As Long Dim tailleTableau As Long Dim pile() As couple
tailleTableau = UBound(t) + 1 - LBound(t) ReDim pile(1 To tailleTableau) '' La taille de la pile peut être nettement moindre '' (de l'ordre de log(tailleTableau). Voir Sedgewick. iPile = 1 pile(iPile).mini = 1 'Premier indice du tableau pile(iPile).maxi = UBound(t) 'Dernier indice du tableau iPile = iPile + 1 ' pour que iPile, à la première itération du do, '' soit égal à 1
Do iPile = iPile - 1 'la pile diminue et le programme '' trie récursivementles parties non triées mini = pile(iPile).mini ' au départ 1 maxi = pile(iPile).maxi ' au départ à la dimension du tableau Do borne1 = mini borne2 = maxi moyen = (mini + maxi) 2 'recuperer la valeur au milieu du tableau tMoyen = t(moyen) Do
'' Invariants de cette boucle : '' borne1 <= borne2 (vrai lors de la première exécution et exigé par la clause de la boucle les fois suivantes) (1) '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (2) '' (Lors de la première exécution de la boucle, borne1 égale mini, donc c'est banal dans ce cas.) '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (3) '' (Lors de la première exécution de la boucle, borne2 égale maxi, donc c'est banal dans ce cas.) '' Il existe un i (<= maxi et) >= borne1 tel que t(i) > tMoyen. (4) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.) '' Il existe un i (>= mini et) <= borne2 tel que t(i) > tMoyen. (5) '' (A la première exécution de cette boucle, c'est vrai avec i = moyen.)
Do While t(borne1) < tMoyen 'recherche d 'un element plus grand borne1 = borne1 + 1 Loop
'' Dans la boucle qui précède, l'usage de < et non de < '' dans "While t(borne1) < tMoyen" '' garantit que borne1 ne montera pas plus haut que le i considéré en (4). '' Cette garantie permet de ne mettre qu'une vérification dans la clause '' de la boucle en question '' et cette vérification est une comparaison entre deux valeurs '' dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne1) >= tMoyen. '' Vu la condition sous laquelle borne1 a été incrémenté, '' (2) est encore vraie, à savoir : '' Pour tout i (>= mini et) < borne1, t(i) <= tMoyen. (6)
Do While t(borne2) > tMoyen 'recherche d 'un element '' plus petit borne2 = borne2 - 1 Loop
'' Dans la boucle qui précède, l'usage de > et non de > dans "While t(borne2) > tMoyen" '' garantit que borne2 ne descendra pas plus bas que le i considéré en (5). '' Cette garantie permet de ne mettre qu'une vérification dans la clause de la boucle en question '' et cette vérification est une comparaison entre deux valeurs dont l'une est fixe : cela est '' favorable à la rapidité de l'exécution.
'' Maintenant, t(borne2) <= tMoyen. '' Vu la condition sous laquelle borne2 a été décrémenté, '' (3) est encore vraie, à savoir : '' Pour tout i (<= maxi et) > borne2, t(i) <= tMoyen. (7) '' En raison de (6), borne2 ne peut pas être descendu plus bas '' que borne1 - 1. Donc : '' borne2 >= borne1 - 1. (8) '' Pour les besoins du commentaire (et non du programme), désignons '' respectivement par borne1bis et borne2bis '' les valeurs actuelles de borne1 et de borne2. '' Il résulte de (6) et (7) que : '' si borne1bis et borne2bis sont égales, t(borne1bis) = t (borne2bis) = tMoyen. (9) If borne1 <= borne2 Then 'si les deux pointeurs ne se rencontrent pas 'permutation des elements designés par les pointeurs tt = t(borne1) t(borne1) = t(borne2) t(borne2) = tt ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ''''''''''''''''' borne1 = borne1 + 1 borne2 = borne2 - 1
End If
'' Les relations (6) et (7) sont encore vraies. '' Dans le cas où borne1bis et borne2bis étaient égales, on a maintenant '' borne1 = borne2 + 2 et t(borne1 + 1) = tMoyen. (10) '' Dans le cas où borne2bis était égal à borne1bis - 1, le If qui précède '' ne s'est pas exécuté, donc '' borne2 = borne1 - 1. (11) '' Dans le cas où borne2bis était égal à borne1bis + 1, on a maintenant '' borne2 = borne1 - 1. (12) '' Dans les autres cas, borne2bis était >= borne1bis + 2, donc borne2 >= borne1; dans ce cas, '' le If qui précède s'est exécuté; la permutation a rendu t(borne1bis) <= tMoyen et la décrémentation '' a rendu borne2 égal à borne2bis - 1, qui est > borne1bis, donc (5) est encore vraie; de même, '' la permutation a rendu t(borne2bis) >= tMoyen et l'incrémentation a rendu borne1 égal à borne1bis + 1, '' qui est < borne2bis, donc (4) est encore vraie. (13) '' Il résulte des relations (10) à (13) que si borne1 < borne2 (ce qui est la condition de répétition de la boucle), '' les relation (4) et (5) sont encore vraies. Comme on a vu que (6) et (7) sont encore vraies, les '' invariants de boucle sont démontrés.
Loop While borne1 <= borne2 'si les pointeurs se chevauchent, 'arrêt de la boucle '' Si, au cours d'une exécution de la boucle qui précède, borne1bis >= borne2bis - 1, la boucle ne se réexécute pas; '' dans le cas contraire, borne1 est incrémenté, borne2 est décrémenté et la relation borne1 <= borne2 est '' conservée. Comme ceci n'est pas possible indéfiniment, la boucle s'arrêtera. '' Alors borne1 > borne2 et une des conditions (10), (11), (12) doit être satisfaite. '' On en tire que tout élément du sous-tableau délimité par [mini, borne2] est <= à tout élément du sous-tableau '' délimité par [borne1, maxi], qu'il y a au plus 1 élément entre ces deux sous-tableaux et que si cet élément '' existe, sa valeur est tMoyen, qui est >= à tout élément du sous-tableau gauche et <= à tout élément du '' sous-tableau droit. Il suffit donc de trier les deux sous-tableaux en question.
If borne2 - mini < maxi - borne1 Then 'stockage dans la pile de la partie de tableau non triée 'on pourrait utiliser un appel récursif de quicksort en 'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de 'la pile et de la récursivité 'ça enlèverait du piment au programme If borne1 < maxi Then pile(iPile).mini = borne1 pile(iPile).maxi = maxi iPile = iPile + 1 'la pile augmente End If maxi = borne2 Else If mini < borne2 Then pile(iPile).mini = mini pile(iPile).maxi = borne2 iPile = iPile + 1 'la pile augmente End If mini = borne1 End If Loop While mini < maxi Loop While iPile <> 1 End Sub
Function partieImpaire(n As Long)
Dim nCopie As Long nCopie = n
Do While nCopie Mod 2 = 0 nCopie = nCopie 2 Loop
partieImpaire = nCopie
End Function
' Encore merci. ' Adrien
Adrien Delcour
Bonjour Pascal. Bien d'accord avec vous sur l'avantage d'éviter la fonction récursive. Comme le disent les manuels, les (rares) mauvais cas du quicksort demandent un temps proportionnel au carré de la taille. Je me souviens l'avoir vérifié avec une version non récursive. Avec une fonction récursive, le même programme me semblait prendre un temps proportionnel au cube de la taille ! Encore merci pour cette excellente version.
-----Message d'origine----- Salut Adrien, Je relève : 'on pourrait utiliser un appel récursif de quicksort en
'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de
'la pile et de la récursivité 'ça enlèverait du piment au programme D'après mes tests, pas seulement, car la récursivité est couteuse en
ressources ce qui n'est pas le cas de cette gestion à la mano de la pile...
-- Amicalement. Pascal "il n'y a pas de vent favorable pour celui qui ne sait pas ou il va."
Sénèque. http://www.ilyapa.net/excel
Bonjour Pascal.
Bien d'accord avec vous sur l'avantage d'éviter la
fonction récursive. Comme le disent les manuels, les
(rares) mauvais cas du quicksort demandent un temps
proportionnel au carré de la taille. Je me souviens
l'avoir vérifié avec une version non récursive. Avec une
fonction récursive, le même programme me semblait prendre
un temps proportionnel au cube de la taille !
Encore merci pour cette excellente version.
-----Message d'origine-----
Salut Adrien,
Je relève :
'on pourrait utiliser un appel récursif de
quicksort en
'remplaçant
'la procédure quicksort par une fonction
'quicksort(borneInf, borneSup) et éviter
ainsi la gestion de
'la pile et de la récursivité
'ça enlèverait du piment au programme
D'après mes tests, pas seulement, car la récursivité est
couteuse en
ressources ce qui n'est pas le cas de cette gestion à la
mano de la pile...
--
Amicalement.
Pascal
"il n'y a pas de vent favorable pour celui qui ne sait
pas ou il va."
Bonjour Pascal. Bien d'accord avec vous sur l'avantage d'éviter la fonction récursive. Comme le disent les manuels, les (rares) mauvais cas du quicksort demandent un temps proportionnel au carré de la taille. Je me souviens l'avoir vérifié avec une version non récursive. Avec une fonction récursive, le même programme me semblait prendre un temps proportionnel au cube de la taille ! Encore merci pour cette excellente version.
-----Message d'origine----- Salut Adrien, Je relève : 'on pourrait utiliser un appel récursif de quicksort en
'remplaçant 'la procédure quicksort par une fonction 'quicksort(borneInf, borneSup) et éviter ainsi la gestion de
'la pile et de la récursivité 'ça enlèverait du piment au programme D'après mes tests, pas seulement, car la récursivité est couteuse en
ressources ce qui n'est pas le cas de cette gestion à la mano de la pile...
-- Amicalement. Pascal "il n'y a pas de vent favorable pour celui qui ne sait pas ou il va."
Sénèque. http://www.ilyapa.net/excel
Geo
Bonjour Adrien et Pascal
Bonjour. [Couic]
Au cas où cela intéresse quelqu'un, voici une rédaction démontrée. [Recouic]
Merci, je me suis imprimé ça pour lire dans le train j'avais mis le courriel de Pascal de côté pour revoir mes macros qui incorporent un tri. Vous me rappelez que je ne l'ai pas fait ;-)
--
A+
Bonjour Adrien et Pascal
Bonjour.
[Couic]
Au cas où cela intéresse quelqu'un, voici une rédaction
démontrée.
[Recouic]
Merci, je me suis imprimé ça pour lire dans le train
j'avais mis le courriel de Pascal de côté pour revoir mes macros qui
incorporent un tri.
Vous me rappelez que je ne l'ai pas fait ;-)
Au cas où cela intéresse quelqu'un, voici une rédaction démontrée. [Recouic]
Merci, je me suis imprimé ça pour lire dans le train j'avais mis le courriel de Pascal de côté pour revoir mes macros qui incorporent un tri. Vous me rappelez que je ne l'ai pas fait ;-)
