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

Ajouter un commentaire

Commentaire

Messages postés
11
Date d'inscription
lundi 26 mars 2007
Statut
Membre
Dernière intervention
17 janvier 2011

Bonjour AlexN,

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.