Algo général de recherche dichotomique après un trie bubble sort

Soyez le premier à donner votre avis sur cette source.

Snippet vu 19 073 fois - Téléchargée 28 fois

Commenter

Contenu du snippet

Le code suivant (écrit en C++) effectue dans un premier temps le Trie Bubble Sort d'un tableau. Par la suite une Recherche Dichotomique (Code en Algo) vient compléter le tout.

Lors d'une recherche Dichotomique la borne supérieure ou inférieure du tableau est modifiée.
Par conséquent, le tableau n'est plus parcouru dans son ensemble, la Recherche en est d'autant Plus Rapide.

Note: Le trie Bubble Sort n'est pas le plus optimisé...

Source / Exemple : 


//Librairies
#include...

//Variables globales
typedef struct
{ char nom_ville[32];
  char nom[32];
  char tel[11];
}Tindex;

Tindex idx[Max];
int j;

/* Trie Bubble Sort - Création d'un Index trié
     en fonction des numéros de téléphones */

void tri_tel_index()
{int k;
Tindex temp[Max];
   for(k=Max-1;k!=0;k--)
   { for(j=0;j<k;j++)
     {   if((strcmp(idx[j].tel,idx[j+1].tel))>0)
          {  temp[0]=idx[j];
            idx[j]=idx[j+1];
            idx[j+1]=temp[0];
            }
       }
    }
j=0;
}

//Prog. principal
void main() {
...
}

Algo Général de la Recherche Dichotomique 

Procedure recherche_dichotomique(par val ent elt, par val ent N, par val ent T[])
Debut
|
|     var inf, sup, m;
|     inf <- 1;
|     sup <- N;
|     m <- (inf+sup) div 2;  
|  /* en C++ m = (int)((inf+sup)/2) */
|                          
|  /* Ici l'astuce : la borne supérieure ou inférieure est modifiée,
|     le tableau n'est plus parcouru dans son ensemble */
| 
|                                  
|    Tant que (T[m] != elt et inf < sup) faire
|    |  
|    |   Si (elt < T[m]) alors 
|    |   | 
|    |   |   sup <- m - 1;
|    |   |
|    |   |   Sinon inf <- m + 1;
|    |   |
|    |   Fin Si
|    |
|    |   m <- (inf + sup) div 2; 
|    | 
|    Fin Tque
|
|    Si (T[m] = elt)
|    |
|    |  Afficher("L'element se trouve à l'indice m") 
|    | 
|    |  Sinon Afficher ("L' élément n'existe pas ")
|    |   
|    Fin Si
|
Fin

Conclusion :


Attention : "La Recherche Dichotomique s'effectue toujours sur un Tableau Trié."

A voir également

Ajouter un commentaire

Commentaires

Signaler
cs_tokaido6
Messages postés
4
Date d'inscription
dimanche 8 juin 2008
Statut
Membre
Dernière intervention
21 octobre 2009
 -
Slt sbeuz,
bravoo pour cet algo, il m'a permis de faire ma recherche dichotomique en c# du premier coup sans bugger.
Merci.
Signaler
uesgui
Messages postés
172
Date d'inscription
vendredi 29 décembre 2000
Statut
Membre
Dernière intervention
10 octobre 2012
 -
Bonjour,
Je suis tout nouveau ici et
J'essaye d'utiliser cet algorithme pour faire une recherche en maths mais j'ai un bug avec Dev C++ a la ligne Tindex idx[Max];
Pourquoi ? Que Faire ?
Merci à vous si vous avez une idée
Signaler
cs_lafamille
Messages postés
1
Date d'inscription
jeudi 22 octobre 2009
Statut
Membre
Dernière intervention
27 janvier 2010
 -
bonjour!!
je me demande a quoi correspond elt et N de l'algo par rapport au tri a bulle du dessus ???
merci a vous
S'inscrire maintenant

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.

Du même auteur (sbeuz)