Tri par insertion avec sentinelle
Soyez le premier à donner votre avis sur cette source.
Snippet vu 12 543 fois - Téléchargée 26 fois
Contenu du snippet
Il s'agit d'un tri classique et peu efficace, mais qui montre l'usage d'une sentinelle.
Source / Exemple :
#include "stdafx.h"
#include "stdlib.h"
#include "time.h"
#define DIM 10
int main(int argc, char* argv[])
{
int i,j, t[DIM+1];
t[1] = 1;
srand(unsigned(time(NULL)));
// Tirage
for ( i = 2; i <= DIM; i++ ) {
j = rand()%i+1;
t[i] = t[j];
t[j] = i;
}
// Affichage
for ( i = 1; i <= DIM; i++ )
printf("t[%d] = %d\n", i, t[i]);
puts("");
// Tri
int aux;
for ( i = 1; i <= DIM - 1; i++ ) {
aux = t [i + 1];
t[0] = aux; // sentinelle
j = i;
while (t[j] > aux) { t[j+1] = t[j]; j = j - 1; }
t[j+1] = aux;
}
// Affichage
for ( i = 1; i <= DIM; i++ )
printf("t[%d] = %d\n", i, t[i]);
return 0;
}
A voir également
- Tri par insertion c++
- Tri par insertion code c++ - Meilleures réponses
- Tri insertion - Meilleures réponses
- Tri par insertion liste chainée en c ✓ - Forum - C++ & C++ .NET
- Tri par insertion java - Forum - Java
- C# / .NET : Tri générique : tri rapide, tri à bulle, tri par sélection - Guide
- Tri par insertion php - Guide
- Tri par insertion sur listes simplement chainées - Forum - C
Commentaire
J'avoue que je n'est pas lancé ton code.
Par contre tout ce qui est de la forme i+1, j= j-1 etc... utilise les opérateur "++" et "--" niveau rapidité c'est les meilleurs ;)
Donc toi tu as:
// Tri
int aux;
for ( i = 1; i <= DIM - 1; i++ ) {
aux = t [i + 1];
t[0] = aux; // sentinelle
j = i;
while (t[j] > aux) { t[j+1] = t[j]; j = j - 1; }
t[j+1] = aux;
}
Moi j'aurais plutôt:
// Tri
int aux;
for ( i = 1; i <= DIM - 1; i++ ) {
aux = t [i++];
t[0] = aux; // sentinelle
j = i;
while (t[j] > aux) { t[j+1] = t[j]; j--; }
t[j++] = aux;
}
ces opérateurs sont implémenté de façon à que le processeur face les calcules beaucoup plus rapidement que avec des i+1, ou i = i +1...
d'ailleur sache que tu peut utiliser aussi ++i ou --i, mais attention le sens est différent de i++ ou i--.
je dis ça peut être tu le sais déjà mais je trouve qu'il vaut mieux optimiser au maximum son code ;) (celà deviens très nécessiteux quand on a de longue boucle.
Autrement ton code manque de beaucoup de commentaires, ce qui pourrais faciliter la lecture de celui-ci. et d'expliquer pourquoi pas ce qu'est une sentinelle pour ceux qui ne savent pas. (comme moi par exemple lol ^^)
Je te fais aucunes reproches ce ne sont que des avis personnel ;)
Cordialement,
Masterweb.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.