Algo de classement

[lisztfr]

Bonjour,

Mon programme de classement ne fonctionne pas, pourquoi ? C'est dur un 1er Janvier..

Des chiffres au hasard dans A[1]-A[10] :

FOR (Z=1;Z=<9;Z++){
FOR(Y=Z;Y=<9;Y++){
IF(A[Y]>A[Y+1] THEN{
SWAP(A[Y],A[Y+1])
}
};A[Z]=A[Y]
}

Oué bien c'était plus facile sur le SHARP 1401 (que sur la Kinpo Hp 9g)

Au passage c'est vrai que les 400 pas de programme ce n'est rien du tout, il m'en reste 224 après ce programme et celui pour générer les chiffres et les revoir, c'est à dire 2 FOR !

[gege]

Euh ben en effet.
C'est parce que tu fais dans le mauvais ordre (explication vaseuse ok).

Code : Tout sélectionner

for (Z=10; Z>1; --Z)
  {
  for (Y=1; Y<Z; ++Y)
    {
    if (A[Y]>A[Y+1])
      {
      SWAP(A[Y],A[Y+1])
      }
    }
  }

N'est-ce pas plus lisible ?
G.E.

EDIT : bon ok, j'essaye d'expliquer. Dans le tri à bulles, tu fais remonter / descendre le plus grand / plus petit, puis tu traites les (n-1) restants. Donc Z doit diminuer et non augmenter.
C'est pas mieux

[lisztfr]

Toujours le même résultat, diviser pour régner qu'ils disaient :

Code : Tout sélectionner

PROG 3
FOR(Z=1;Z=<9;Z++){
  GOSUB PROG 4; A[Z]=A[Y]
}

PROG 4
FOR(Y=Z;Y=<9;Y++){
  IF(A[Y]>A[Y+1] THEN{
     SWAP(A[Y],A[Y+1])
}
}

Il me met la valeur maximale partout ...

L'algo n'est pas bon il faut (PROG 4):

IF(A[Z]>A[Y+1] THEN

Et encore il y a une erreur

[bernouilli92]

Pourquoi tu mets A[Z]=A[Y] après l'appel au sous programme ?

[lisztfr]

Programme pour générer les chiffres aléatoires :

Code : Tout sélectionner

FOR(Z=1;Z=<10;Z++){A[Z]=RANDI(1,10)
}

Pour visionner ces chiffres :

Code : Tout sélectionner

FOR(Z=1;Z=<10;Z++){PRINT Z, " ",A[Z];SLEEP(1)
}

Pour les classer :

Code : Tout sélectionner

PROG 3
FOR(Z=1;Z=<9;Z++){GOSUB PROG 4
}

PROG 4
FOR(Y=Z;Y=<10;Y++){IF A[Z]>A[Y] THEN{
  SWAP(A[Z],A[Y])
}
}

Voilà, j'en suis à 228 pas de programme, sur 400, dont 10 pour autre chose, donc ces bricoles-là prennent (400 -10) - 228 = 162 pas de programme, eh oui ! bravo, j'espère que les gars se sont bien enrichis parce que juste mettre un peu plus de mémoire ça n'aurait pas coûté tellement plus cher...

[lisztfr]

Pourquoi tu mets A[Z]=A[Y] après l'appel au sous programme ?

Parce que ... j'ai mieux compris l'algo.

comparer A(y) > A(Y+1), si c'est 3 > 2 j'ai le swap et alors, A(y+1) vaut 3 ce qui n'est pas bon puisque je sélectionne le plus gros chiffre et le pousse vers le haut.

Donc il suffit de maintenir le plus petit chiffre au même endroit càd, A(Z)...

[jxano]

À mon avis :

FOR (Z=1;Z=<8;Z++){
FOR(Y=Z+1;Y=<9;Y++){
IF(A[Y]>A[Y+1] THEN{
SWAP(A[Y],A[Y+1])
}
};A[Z]=A[Y]
}

Ça marchera mieux.

[lisztfr]

C'est passionnant la programmation n'est-ce pas ?

Me demande ce que ça donne sur une HP-67, ou une 602P

M'enfin... à cause des limites de cette puce, qui est dédié au graphisme, il n'y a pas bcp de mémoire. les autres Citizen avec 1200 pas de prog sont à considérer, quoiqu'elles me paraissent plus grandes.

[bernouilli92]

À mon avis :

FOR (Z=1;Z=<8;Z++){
FOR(Y=Z+1;Y=<9;Y++){
IF(A[Y]>A[Y+1] THEN{
SWAP(A[Y],A[Y+1])
}
};A[Z]=A[Y]
}

Ça marchera mieux.

Je ne penses pas.
Lors de la première boucle (Z=1), la boucle Y va parcourir les éléments 2 à 10 et faire des opérations dessus, une fois cette boucle finie, on écrase A[1] par un élément de l'ensemble A[2] à A[10].
On duplique une valeur et on en perd une.

[jxano]

Je n'ai pas fais gaffe aux indices de tableau...

[lisztfr]

Effectivement il existe un algo du type gégé, il reste à le mettre au point...

Une fenêtre de 2 indices consécutifs monte et redescend.

[badaze]

J'avais fait un petit programme en php sans boucle for.

Code : Tout sélectionner

<?php

$arr=array(67,32,1,87,88,-3,123,565,-32,45,99,16,78,43,-638,33,61,90,0,12);

$Change   = false;
$Continue = true;
$Count    = count($arr);
$i = 0;
while ($Continue) {
	if ($i >= $Count-1) {
		$i = 0;
		if ($Change == false) {
			$Continue = false;
		}
		$Change = false;
	} 
		if ($arr[$i] > $arr[$i+1]) {
			$Temp      = $arr[$i];
			$arr[$i]   = $arr[$i+1];
			$arr[$i+1] = $Temp;
			$Change    = true;
		}
	$i++;
}

print "Fin : <br/>";
print_r($arr);
print "<br/>";
?>

[bernouilli92]

Un algo simple de ce type est de parcourir le tableau deux à deux, inverser les deux élément successifs si nécessaire. Refaire cette opération tant qu'il y a quelque chose à faire, une façon de voir s'il reste des choses à faire est d'avoir un flag qu'on mets à 1 dès qu'on effectue une inversion.
On recommence tant que ce flag est à 1.

Cela pourrait donner quelque chose de comme ceci:

Code : Tout sélectionner

DO
  Y=0;
  FOR (Z=1;Z<10;Z++) {
    IF (A[Z]>A[Z+1]) THEN {
      SWAP(A[Z],A[Z+1]);
      Y=1;
    }
  }
UNTIL Y==0;

[gege]

Oui mais c'est encore plus inefficace que le tri à bulles ci-dessus...
Je me demande dans quelle mesure ?
G.E.

[bernouilli92]

Ça dépend beaucoup de l'ordre des nombre.
Le tri précédent fonctionne en un nombre de boucles déterminé (n*(n+1)/2) alors ce tri là peut très bien se finir au bout de n boucles. Je pense que le Max de boucle est n*n.
Et donc c'est entre les deux en fonction de l'ordre initial des nombres.
Dans les deux cas c'est en O(n^2), pas terrible.