Algo de classement

[Forthman]

moi je m'amusais avec mon HECTOR (fin des années 80 )

[lisztfr]

C'est ça que j'avais en tête en fait :

http://en.wikipedia.org/wiki/Cocktail_sort

Cocktail sort is a slight variation of bubble sort. It differs in that instead of repeatedly passing through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. It can achieve slightly better performance than a standard bubble sort.

Mais il faut remettre les indices normaux, 1-9, 8-2...

[BubbleBobble]

Si les algos de tri vous font kiffer, je vous recommande la lecture du volume 3 de "the art of computer programming" de Donald E.Knuth (edité par Addison Wesley). Il est sous-titré "sorting and searching". Il n'y a que ça sur près de 800 pages.

Pierre

[badaze]

Si les algos de tri vous font kiffer, je vous recommande la lecture du volume 3 de "the art of computer programming" de Donald E.Knuth (edité par Addison Wesley). Il est sous-titré "sorting and searching". Il n'y a que ça sur près de 800 pages.

Pierre

Est-ce qu'il faut faire le tri de toutes les informations fournies ?

[lisztfr]

Un programme doit toujours pouvoir se désassembler (démonter), c'est ce qui va me donner le courage de réécrire mon prog de 1450 lignes en Q basic...

Remonter des SUB aux DIM, TYPE, (en gros des headers). C'est pire que du désossage....

Chaque SUB doit avoir sa fiche sanitaire, son parcours de soins, carnet de santé.

[C.Ret]

[...]Mais il faut remettre les indices normaux, 1-9, 8-2...

Moi aussi j'ai un petit faible pour ce tri.
En fait pas besion d'utiliser des indices de 1 à n, tout fonctionne aussi bien avec des indices entre 0 et n...

En fait, comme pour tout les algorithmes, les nombres à trier sont repèrés par leur indice. Rien n'empêche de généraliser, par exemple entre les indices a et b quelconques. Par exemple entre -50 et 2345 ! peu importe.

Pour le tri coktail, j'ai un pseuod-code bien sympathique qui se distingue des codes publiés ici et là qui souvent utilise des flag, des indicateurs de permutation et souvent un test A(i)<A(j) et A(i)>A(j).

Alors qu'il existe un moyen de programmer cela de façon plus concise:

Comme pour mon psot précédant , I désigne le compteur d'étapes du tri et J est l'indice des éléments du tableau A comparés.
Mais cette faois, il y a un sens S qui vaut +1 vers la gauche et -1 vers la droite. Dans tous les cas J prend les valeurs entre A et B

Je supose que l'on souhaite trier les valeurs entre les indices a et b du tableau :

Code : Tout sélectionner

DIM A( a TO b )

S=1 : A=a : B=b-1
FOR I=1 TO b-a DO
   FOR J=A TO B STEP S DO
      IF  A(J)>A(J+1)  THEN  SWAP A(J),A(J+1)
   NEXT J
   S=-S : SWAP A,B : A=A+S
NEXT I

Pour un tableau complet indicé de 0 à n, il suffit de copier ce code avec a=0 et b=n.
Pour les tableaux numéroté de 1 à N, il suffit de recopier avec a=1 et b=N
Pour les tableau indicés entre -50 et 2345, il suffit de prendre a=-50 et b=2345

Tout cela pour montrer que ni les algorithmes ni les programmes ne dépendent des bornes d'indices.

Mais bon, je n'apprends rien à un utilisateur de QBasic qui est l'un des rares BASIC où l'on peut définir la plage d'indice dans les déclarations DIM !


Exemple:

Code : Tout sélectionner

N     S    A    B    I   J     A1  A2  A3  A4  A5    
5                              8   3   5   2   1
5     +1   1    4              8   3   5   2   1   initialisation S A et B
5                    1                             Première étape (boucle FOR I) avec S=+1
5                        1=A   3 - 8   3   2   1   swap 8 et 3
5                        2     3   5 - 8   2   1   swap 8 et 5  ...la grosse bête qui monte qui monte !
5                        3     3   5   2 - 8   1   swap 8 et 2
5                        4=B   3   5   2   1 - 8   swap 8 et 1     la grosse bête est montée tout en haut :)
5     -1   3    1
5                    2                             Seconde étape (boucle FOR I)  S=-1 décreschendo
5                        3=A   3   5   1 - 2   8   swap 2 et 1 
5                        2     3   1 - 5   2   8   swap 5 et 1 ...la petite bête qui tombe qui tombe !
5                        1=B   1 - 3   5   2   8   swap 3 et 1    la petite bête est en bas !
5     +1   2    3  
5                    3                             Troisième étape (boucle FOR I)
5                        2=A   1   3   5   2   8   compare 3 et 5 pas de swap !
5                        3=B   1   3   2 - 5   8   swap 5 et 2
5     -1   2    2    
5                    4                             Quatrième et dernière étape
5                        2=A=B 1   2 - 3   5   8   swap 3 et 2  

Fin du programme, la liste     1   2   3   5   8   est triée !

[gege]

Bonjour,
Je ne vois pas trop la différence avec le tri à bulles classique (en termes de nombre d'étapes bien sûr) ?
Le principe est aussi plutôt identique ?

G.E.

[lisztfr]

Bonjour,
Je ne vois pas trop la différence avec le tri à bulles classique (en termes de nombre d'étapes bien sûr) ?
Le principe est aussi plutôt identique ?

G.E.

En ce qui concerne mon code ? il n'y en a pas.

Le fait de trier les pairs puis les impairs peut intéresser les machines à architectures parallèle..

[badaze]

Le programme gégé enfin réalisé :

Code : Tout sélectionner

PROG 3
U=1;V=2; "initialisation
  Lbl 1:
  IF(U+V==3)THEN{GOSUB PROG 4;};
  IF(U+V>=4)THEN{GOSUB PROG 5;};
  IF(U+V==2)THEN {PRINT "ABC";END};
  GOTO 1
END

PROG 4
U=0;V=4;
  FOR(Y=1;Y=<5;Y++){
  Z= Y*2 - 1;
  GOSUB PROG 6;};
END

PROG 5
U=0;V=2;
  FOR(Y=4;Y>=1;Z--){
  Z= Y*2;
  GOSUB PROG 6;};
END

PROG 6
X=Z+1;
IF(A[Z]>A[X]) THEN{
    SWAP(A[Z],A[X]);
    U=1;
};

Il compare les éléments (1,2), (3,4) etc en montant et (8,9), (6,7) en descendant
De cette manière on contrôle mieux ce qu'on fait, que de faire glisser une fenêtre de façon continue.

La condition de sortie U+V==2 oblige le programme à s'arrêter après le parcours complet des 2 boucles sans changement.

Tout cela n'est pas bon parce que si j'ai 15 él. le programme ne suit pas.... Mais cela prendrait encore beaucoup de lignes de codes.

Si ton algo est dépendant du nombre d'éléments alors ce n'est pas un bon algo. Je ne comprends pas cette partition entre haut et bas.

Changer FOR(Y=4;Y>=1;Z--){ en FOR(Y=4;Y>=1;Y--){

[lisztfr]

Le programme gégé enfin réalisé :

La condition de sortie U+V==2 oblige le programme à s'arrêter après le parcours complet des 2 boucles sans changement.

Tout cela n'est pas bon parce que si j'ai 15 él. le programme ne suit pas.... Mais cela prendrait encore beaucoup de lignes de codes.

Si ton algo est dépendant du nombre d'éléments alors ce n'est pas un bon algo. Je ne comprends pas cette partition entre haut et bas.

J'ai corrigé, merci...

Il s'agit du tri pair-impair (odd-even). Je croyais que ce serais plus efficace mais non (ça dépend du degré de désordre...)

Il classe d'abord les couples impairs (1/2, 3/4,....), puis les couples pairs, en sens inverse ( 8/9, 6/7, 4/5, 2/3) de sorte que tous les classements se chevauchent... Mais c'était inutile de le faire en sens inverse.

Ca aurait été utile si j'avais eu une fenêtre glissante d'un él à chaque fois, ex :

2, 10, 1, en descendant le classement se fait en UNE fois.

Bon, pour que ça fonctionne avec N éléments il aurait fallu éditer Y en fonction de N....pas trop compliqué.

Ce qui m'a causé le plus de souci c'est

- SWAP qui n'évalue pas l'indice A[Z+1], alors que les comparateurs >, <, ==, =/= le font.
- L'astuce avec U, V, il ne faut négliger aucun cas...

[C.Ret]

Bonjour,
Je ne vois pas trop la différence avec le tri à bulles classique (en termes de nombre d'étapes bien sûr) ?
Le principe est aussi plutôt identique ?

G.E.

Tout à fait !
En fait tous ces variations d'algo de tri dérvé du "tri à bulles" n'ont aucune autre raison d'exister qu'autant qu'outil pédagogique et théorique. Dans la pratique, on se moque bien des 'tortues' et des 'renards' !


C'est pour cela que le "tri à bulles" persiste à exister; c'est une méthode simple, une liste à trier , deux boucles emboîtée, un test et un échange des donnée; et le tour est joué. Pas à se casser la nénette !
Et c'est comme cela que souvent, je "simplifie" en utilisant la version avec A(I) et A(J) !

[lisztfr]

C'est pour cela que le "tri à bulles" persiste à exister;

Oui, j'avais un cas où je voulais juste extraire les 20 plus grands éléments d'une liste de 200. Inutile de classer toute la liste, les I, J x20 suffisent.

Une autre question intéressante est la compression... Huffman, etc... c'est encore à propos d'ordre

[lisztfr]

Simplification :

Code : Tout sélectionner

PROG 3
U=1; "initialisation
  Lbl 1:
  GOSUB PROG 4;
  GOSUB PROG 5;
  IF(U==0)THEN {PRINT "ABC";END};
  GOTO 1
END

PROG 4
U=0;
  FOR(Y=1;Y=<5;Y++){
  Z= Y*2 - 1;
  GOSUB PROG 6;};
END

PROG 5
U=0;
  FOR(Y=4;Y>=1;Y--){
  Z= Y*2;
  GOSUB PROG 6;};
END

PROG 6
X=Z+1;
IF(A[Z]>A[X]) THEN{
    SWAP(A[Z],A[X]);
    U=1;
};

[lisztfr]

Simplification :

Code : Tout sélectionner

PROG 3
  Lbl 1:
  U=0;
  FOR(Y=1;Y=<5;Y++){
  Z=Y*2-1;
  GOSUB PROG 6;};

  FOR(Y=4;Y>=1;Y--){
  Z=Y*2;
  GOSUB PROG 6;};

  IF(U==0)THEN {PRINT "ABC";END};
  GOTO 1
END

PROG 6
X=Z+1;
IF(A[Z]>A[X]) THEN{
    SWAP(A[Z],A[X]);
    U=1;
};

Ne peut traiter que les listes de longueur pair.

Il y a l'autre algo qui me taraude...

[lisztfr]

Celui là, le vrai :

Code : Tout sélectionner

PROG 4
  S=1;T=10; 
  Lbl 1:;U=0;
  FOR(Z=S;Z=<T;Z++){X=Z+1;GOSUB PROG 6};
  T=T-1
  FOR(Z=T;Z>=S;Z--){X=Z-1;GOSUB PROG 6};
  S=S+1
  IF(U==0)THEN{PRINT "ABC";END}
  GOTO 1;
END

PROG 6

IF(A[Z]>A[X]) THEN{
    SWAP(A[Z],A[X]);
    U=1;
};