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

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

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)