Tri par insertion avec sentinelle
0/5 (1 avis)
Snippet vu 13 560 fois - Téléchargée 28 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 code c++
- Tri par insertion c# - Guide
- Tri_par_insertion - Codes sources - C / C++ / C++.NET (Maths & Algorithmes)
- PHP : Tri par insertion - CodeS SourceS - Guide
- Visual Basic / VB.NET : Tri par insertion - CodeS SourceS - Guide
- Tri par insertion sur liste simplement chainée ✓ - Forum - C++ & C++ .NET
2 nov. 2009 à 11:24
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.