Plauger implémente qsort en déclarant un tableau local d'une taille de
256 bytes. Ce tableau sert à faire des transpositions (swap) de clés.
Mais comme la taille size des données est inconnue, le code doit, le cas
échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui doit
être assez couteux. Alors je me demandais pourquoi il n'avait pas décidé
d'utiliser malloc pour éviter toutes ses contorsions. Quelque chose dans
la norme l'interdit-t-il ? En plus, il s'agirait d'allouer juste une
fois un buffer dynamique qui permet de faire un swap de façon classique.
Donc, si j'ai bien compris, plus efficace car qsort copiera alors des adresses plutôt que des (éventuellement grosses) structures ?
Tout a fait. De toutes facons, si tu utilises qsort pour trier de grosses structures, tes perf vont etre plombees par les copies de structures...
Faut bien voir que tu vas faire O(n log n) echanges en moyenne... C'est pas comme si quicksort trouvait directement ou il faut mettre chaque element.
Si le temps de comparaison est faible devant le temps d'echange, un bete tri par insertion sera plus efficace...
(insertion: O(n) echanges, O(n2) comparaisons. quicksort: O(n log n) echanges, O(n log n) comparaisons, en moyenne mergesort: O(n log n) echanges, O(n log n) comparaisons, garanti, mais constante plus grande que le quicksort, et surtout espace double requis...)
In article <49218432$0$15993$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:
Donc, si j'ai bien compris, plus efficace car qsort copiera alors des
adresses plutôt que des (éventuellement grosses) structures ?
Tout a fait. De toutes facons, si tu utilises qsort pour trier de grosses
structures, tes perf vont etre plombees par les copies de structures...
Faut bien voir que tu vas faire O(n log n) echanges en moyenne... C'est
pas comme si quicksort trouvait directement ou il faut mettre chaque element.
Si le temps de comparaison est faible devant le temps d'echange,
un bete tri par insertion sera plus efficace...
(insertion: O(n) echanges, O(n2) comparaisons.
quicksort: O(n log n) echanges, O(n log n) comparaisons, en moyenne
mergesort: O(n log n) echanges, O(n log n) comparaisons, garanti, mais
constante plus grande que le quicksort, et surtout espace double requis...)
Donc, si j'ai bien compris, plus efficace car qsort copiera alors des adresses plutôt que des (éventuellement grosses) structures ?
Tout a fait. De toutes facons, si tu utilises qsort pour trier de grosses structures, tes perf vont etre plombees par les copies de structures...
Faut bien voir que tu vas faire O(n log n) echanges en moyenne... C'est pas comme si quicksort trouvait directement ou il faut mettre chaque element.
Si le temps de comparaison est faible devant le temps d'echange, un bete tri par insertion sera plus efficace...
(insertion: O(n) echanges, O(n2) comparaisons. quicksort: O(n log n) echanges, O(n log n) comparaisons, en moyenne mergesort: O(n log n) echanges, O(n log n) comparaisons, garanti, mais constante plus grande que le quicksort, et surtout espace double requis...)
candide
Marc Espie a écrit :
(insertion: O(n) echanges, O(n2) comparaisons.
Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A moins que les items à trier ne soient implémentés sous forme d'une liste chainée auquel cas il y a n insertions.
Marc Espie a écrit :
(insertion: O(n) echanges, O(n2) comparaisons.
Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo
du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A
moins que les items à trier ne soient implémentés sous forme d'une liste
chainée auquel cas il y a n insertions.
Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A moins que les items à trier ne soient implémentés sous forme d'une liste chainée auquel cas il y a n insertions.
espie
In article <49218f68$0$19726$, candide wrote:
Marc Espie a écrit :
(insertion: O(n) echanges, O(n2) comparaisons.
Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A moins que les items à trier ne soient implémentés sous forme d'une liste chainée auquel cas il y a n insertions.
Ah ouais, non, erreur de nommage, c'est une variation triviale sur le tri par insertion qui consiste a ne deplacer un element que si tu es sur que c'est le plus petit, puis a faire pareil sur le tableau de n-1 elements...
In article <49218f68$0$19726$426a34cc@news.free.fr>,
candide <candide@free.invalid> wrote:
Marc Espie a écrit :
(insertion: O(n) echanges, O(n2) comparaisons.
Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo
du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A
moins que les items à trier ne soient implémentés sous forme d'une liste
chainée auquel cas il y a n insertions.
Ah ouais, non, erreur de nommage, c'est une variation triviale sur le tri
par insertion qui consiste a ne deplacer un element que si tu es sur que
c'est le plus petit, puis a faire pareil sur le tableau de n-1 elements...
Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A moins que les items à trier ne soient implémentés sous forme d'une liste chainée auquel cas il y a n insertions.
Ah ouais, non, erreur de nommage, c'est une variation triviale sur le tri par insertion qui consiste a ne deplacer un element que si tu es sur que c'est le plus petit, puis a faire pareil sur le tableau de n-1 elements...
Jean-Marc Bourguet
(Marc Espie) writes:
In article <49218f68$0$19726$, candide wrote: >Marc Espie a écrit : > >> >> (insertion: O(n) echanges, O(n2) comparaisons. > >Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo >du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A >moins que les items à trier ne soient implémentés sous forme d'une liste >chainée auquel cas il y a n insertions.
Ah ouais, non, erreur de nommage, c'est une variation triviale sur le tri par insertion qui consiste a ne deplacer un element que si tu es sur que c'est le plus petit, puis a faire pareil sur le tableau de n-1 elements...
J'ai vu cette variation appelee tri par selection.
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
espie@lain.home (Marc Espie) writes:
In article <49218f68$0$19726$426a34cc@news.free.fr>,
candide <candide@free.invalid> wrote:
>Marc Espie a écrit :
>
>>
>> (insertion: O(n) echanges, O(n2) comparaisons.
>
>Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo
>du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A
>moins que les items à trier ne soient implémentés sous forme d'une liste
>chainée auquel cas il y a n insertions.
Ah ouais, non, erreur de nommage, c'est une variation triviale sur le tri
par insertion qui consiste a ne deplacer un element que si tu es sur que
c'est le plus petit, puis a faire pareil sur le tableau de n-1 elements...
J'ai vu cette variation appelee tri par selection.
A+
--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
In article <49218f68$0$19726$, candide wrote: >Marc Espie a écrit : > >> >> (insertion: O(n) echanges, O(n2) comparaisons. > >Tu es sûr ? Parce qu'en moyenne un tri par insertion, c'est grosso modo >du (1/2)(1+2+...+n-1) déplacements d'items ce qui est quadratique. A >moins que les items à trier ne soient implémentés sous forme d'une liste >chainée auquel cas il y a n insertions.
Ah ouais, non, erreur de nommage, c'est une variation triviale sur le tri par insertion qui consiste a ne deplacer un element que si tu es sur que c'est le plus petit, puis a faire pareil sur le tableau de n-1 elements...
J'ai vu cette variation appelee tri par selection.
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
ld
On 17 nov, 13:41, candide wrote:
ld a écrit :
> (...) S'il s'agit de > quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échange r deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
si tu as en plus une connaissance sur l'alignement des elements a swapper (ce qui peut se calculer), il est possible d'ecrire des specializations plus efficaces toujours sans tampon.
Le quicksort que tu as montre n'est pas ce qui se fait de mieux, de loin.
a+, ld.
On 17 nov, 13:41, candide <cand...@free.invalid> wrote:
ld a écrit :
> (...) S'il s'agit de
> quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échange r
deux valeurs sans avoir une zone de "transit", un tampon donc, aussi
petit soit-il.
si tu as en plus une connaissance sur l'alignement des elements a
swapper (ce qui peut se calculer), il est possible d'ecrire des
specializations plus efficaces toujours sans tampon.
Le quicksort que tu as montre n'est pas ce qui se fait de mieux, de
loin.
> (...) S'il s'agit de > quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échange r deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
si tu as en plus une connaissance sur l'alignement des elements a swapper (ce qui peut se calculer), il est possible d'ecrire des specializations plus efficaces toujours sans tampon.
Le quicksort que tu as montre n'est pas ce qui se fait de mieux, de loin.
a+, ld.
candide
ld a écrit :
Ton nom ld me disait quelque chose, ah! je viens de réaliser que tu es Laurent Deniau.
OK, pour moi, tu utilises un tampon ... d'un caractère. Au passage, je ne connais pas vraiment inline (ni restrict) car je me cantonne à C90.
Ta façon de procéder n'est-elle pas très lente (sans inline donc)?
Est-il "académique" d'implémenter qsort sans tampon (avec ta méthode) ? (j'aime utiliser les procédés éprouvés, ça m'économise les neurones ;) )
Le quicksort que tu as montre n'est pas ce qui se fait de mieux, de loin.
Qu'est-ce qui du point de vue du codage C ne te parait pas convenable dans l'implémentation de Plauger (je ne parle pas de l'algorithme, choix du pivot et toutes les optimisations de nature algorithmique qu'on pourrait ajouter) ?
ld a écrit :
Ton nom ld me disait quelque chose, ah! je viens de réaliser que tu es
Laurent Deniau.
OK, pour moi, tu utilises un tampon ... d'un caractère. Au passage, je
ne connais pas vraiment inline (ni restrict) car je me cantonne à C90.
Ta façon de procéder n'est-elle pas très lente (sans inline donc)?
Est-il "académique" d'implémenter qsort sans tampon (avec ta méthode) ?
(j'aime utiliser les procédés éprouvés, ça m'économise les neurones ;) )
Le quicksort que tu as montre n'est pas ce qui se fait de mieux, de
loin.
Qu'est-ce qui du point de vue du codage C ne te parait pas convenable
dans l'implémentation de Plauger (je ne parle pas de l'algorithme, choix
du pivot et toutes les optimisations de nature algorithmique qu'on
pourrait ajouter) ?
OK, pour moi, tu utilises un tampon ... d'un caractère. Au passage, je ne connais pas vraiment inline (ni restrict) car je me cantonne à C90.
Ta façon de procéder n'est-elle pas très lente (sans inline donc)?
Est-il "académique" d'implémenter qsort sans tampon (avec ta méthode) ? (j'aime utiliser les procédés éprouvés, ça m'économise les neurones ;) )
Le quicksort que tu as montre n'est pas ce qui se fait de mieux, de loin.
Qu'est-ce qui du point de vue du codage C ne te parait pas convenable dans l'implémentation de Plauger (je ne parle pas de l'algorithme, choix du pivot et toutes les optimisations de nature algorithmique qu'on pourrait ajouter) ?
Pierre Maurette
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
-- Pierre Maurette
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger
deux valeurs sans avoir une zone de "transit", un tampon donc, aussi
petit soit-il.
Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
-- Pierre Maurette
espie
In article , Pierre Maurette wrote:
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow, je te rappelle qu'il peut se passer un peu n'importe cas, en particulier levee d'exception et terminaison brutale du programme.
In article <mn.a3f67d8b15e2a652.79899@wanadoo.fr>,
Pierre Maurette <maurettepierre@wanadoo.fr> wrote:
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger
deux valeurs sans avoir une zone de "transit", un tampon donc, aussi
petit soit-il.
Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow,
je te rappelle qu'il peut se passer un peu n'importe cas, en particulier
levee d'exception et terminaison brutale du programme.
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow, je te rappelle qu'il peut se passer un peu n'importe cas, en particulier levee d'exception et terminaison brutale du programme.
Charlie Gordon
"Marc Espie" a écrit dans le message de news: gg48v6$jeq$
In article , Pierre Maurette wrote:
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow, je te rappelle qu'il peut se passer un peu n'importe cas, en particulier levee d'exception et terminaison brutale du programme.
Pour éviter cela, il suffit d'utiliser le type unsigned char. En fait le probleme avec ce "classique" est qu'il ne fonctionne pas si a et b sont la meme variable. La valeur est alors forcée à zero. Une variante consiste à utiliser le ou exclusif: #define SWAP(a, b) ((a)^=(b), (b)^=(a), (a)^=(b))
Notons aussi que ni l'un ni l'autre ne fonctionne pour des variables non entières (float...) Enfin il n'est pas prudent d'oublier les parenthèses extérieures dans l'expansion de cette macro.
-- Chqrlie.
"Marc Espie" <espie@lain.home> a écrit dans le message de news:
gg48v6$jeq$1@biggoron.nerim.net...
In article <mn.a3f67d8b15e2a652.79899@wanadoo.fr>,
Pierre Maurette <maurettepierre@wanadoo.fr> wrote:
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger
deux valeurs sans avoir une zone de "transit", un tampon donc, aussi
petit soit-il.
Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow,
je te rappelle qu'il peut se passer un peu n'importe cas, en particulier
levee d'exception et terminaison brutale du programme.
Pour éviter cela, il suffit d'utiliser le type unsigned char.
En fait le probleme avec ce "classique" est qu'il ne fonctionne pas si a et
b sont la meme variable. La valeur est alors forcée à zero.
Une variante consiste à utiliser le ou exclusif:
#define SWAP(a, b) ((a)^=(b), (b)^=(a), (a)^=(b))
Notons aussi que ni l'un ni l'autre ne fonctionne pour des variables non
entières (float...)
Enfin il n'est pas prudent d'oublier les parenthèses extérieures dans
l'expansion de cette macro.
"Marc Espie" a écrit dans le message de news: gg48v6$jeq$
In article , Pierre Maurette wrote:
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow, je te rappelle qu'il peut se passer un peu n'importe cas, en particulier levee d'exception et terminaison brutale du programme.
Pour éviter cela, il suffit d'utiliser le type unsigned char. En fait le probleme avec ce "classique" est qu'il ne fonctionne pas si a et b sont la meme variable. La valeur est alors forcée à zero. Une variante consiste à utiliser le ou exclusif: #define SWAP(a, b) ((a)^=(b), (b)^=(a), (a)^=(b))
Notons aussi que ni l'un ni l'autre ne fonctionne pour des variables non entières (float...) Enfin il n'est pas prudent d'oublier les parenthèses extérieures dans l'expansion de cette macro.
-- Chqrlie.
Pierre Maurette
Marc Espie, le 20/11/2008 a écrit :
In article , Pierre Maurette wrote:
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow, je te rappelle qu'il peut se passer un peu n'importe cas, en particulier levee d'exception et terminaison brutale du programme.
Bien entendu. Je ne peux l'ignorer, puisque c'est rappelé sur f.c.l.c tous les deux ou trois jours. J'ai pris soin d'écrire que ce code était défectueux - en C portable -, et seulement en renvoi, j'ai signalé qu'il marchera dans "beaucoup de cas". J'ai rapidement testé par acquit de conscience avec VC, 32bit et 64bit, et gcc 4.3.2, Ubuntu x86-64. Je me demande quelles précautions oratoires faut-il prendre pour ne pas provoquer ce genre de réponse. Peut-être écrire soi-même la réponse dans le message, tant cette réponse est prévisible et était attendue? Ou alors décider que ce petit truc assez amusant et qui ponctuellement peut être pratique n'est pas digne d'intéresser quiconque sur f.c.l.c. et le remettre dans sa culotte ?
-- Pierre Maurette
Marc Espie, le 20/11/2008 a écrit :
In article <mn.a3f67d8b15e2a652.79899@wanadoo.fr>,
Pierre Maurette <maurettepierre@wanadoo.fr> wrote:
candide, le 17/11/2008 a écrit :
ld a écrit :
(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger
deux valeurs sans avoir une zone de "transit", un tampon donc, aussi
petit soit-il.
Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow,
je te rappelle qu'il peut se passer un peu n'importe cas, en particulier
levee d'exception et terminaison brutale du programme.
Bien entendu. Je ne peux l'ignorer, puisque c'est rappelé sur f.c.l.c
tous les deux ou trois jours.
J'ai pris soin d'écrire que ce code était défectueux - en C portable -,
et seulement en renvoi, j'ai signalé qu'il marchera dans "beaucoup de
cas". J'ai rapidement testé par acquit de conscience avec VC, 32bit et
64bit, et gcc 4.3.2, Ubuntu x86-64.
Je me demande quelles précautions oratoires faut-il prendre pour ne pas
provoquer ce genre de réponse. Peut-être écrire soi-même la réponse
dans le message, tant cette réponse est prévisible et était attendue?
Ou alors décider que ce petit truc assez amusant et qui ponctuellement
peut être pratique n'est pas digne d'intéresser quiconque sur f.c.l.c.
et le remettre dans sa culotte ?
(...) S'il s'agit de quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger deux valeurs sans avoir une zone de "transit", un tampon donc, aussi petit soit-il.
Un grand classique, pas exempt de défauts(*): #define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)
(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.
Euh non, pas avec des nombres signes, en tout cas. En cas d'overflow, je te rappelle qu'il peut se passer un peu n'importe cas, en particulier levee d'exception et terminaison brutale du programme.
Bien entendu. Je ne peux l'ignorer, puisque c'est rappelé sur f.c.l.c tous les deux ou trois jours. J'ai pris soin d'écrire que ce code était défectueux - en C portable -, et seulement en renvoi, j'ai signalé qu'il marchera dans "beaucoup de cas". J'ai rapidement testé par acquit de conscience avec VC, 32bit et 64bit, et gcc 4.3.2, Ubuntu x86-64. Je me demande quelles précautions oratoires faut-il prendre pour ne pas provoquer ce genre de réponse. Peut-être écrire soi-même la réponse dans le message, tant cette réponse est prévisible et était attendue? Ou alors décider que ce petit truc assez amusant et qui ponctuellement peut être pratique n'est pas digne d'intéresser quiconque sur f.c.l.c. et le remettre dans sa culotte ?
