Scribd
Importer
41 vues5 pages

Tri Recherche

Ce document décrit plusieurs algorithmes de tri et de recherche tels que le tri par sélection, le tri à bulles, le tri par insertion, le tri shell, le quicksort et la recherche binaire.

Transféré par

Abdelilah Souiri
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
41 vues5 pages

Tri Recherche

Ce document décrit plusieurs algorithmes de tri et de recherche tels que le tri par sélection, le tri à bulles, le tri par insertion, le tri shell, le quicksort et la recherche binaire.

Transféré par

Abdelilah Souiri
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Les algorithmes de tri et de recherche

[Link] du tableau :
int* createArray(int n)
{

int* t=(int*)malloc(n*sizeof(int));

for(int i=0;i<n;i++)
{
printf("T[i]: \n",i+1);
scanf("%d",&t[i]);
}
return t;
}

[Link] afficher

void afficher(int* t,int n)


{
for(int i=0;i<n;i++)
{
printf("%d \t",*(t+i));
}
}

[Link] echanger

void echanger(int *a,int *b)


{
int temp=*a;

*a=*b;
*b=temp;
}
triParSelection
void triParSelection(int tab[],int n)
{

int i,j,index;

for(i=0;i<n-1;i++)
{
index=i;

for(j=i+1;j<n;j++)

if(tab[j]< tab[index])

index=j;

echanger(&tab[i],&tab[index]);
}

}
triBulles
void triBulles(int tab[],int n)
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(tab[j] < tab[i])
echanger(&tab[i],&tab[j]);
}

}
}

TriParInsertion
void TriParInsertion(int tab[], int n) {

for (int i = 1; i < n; i++) {


int el = tab[i];
int j=i;

for(;j > 0 && tab[j - 1] > el;j--) {


tab[j] = tab[j - 1];
}

tab[j] = el;
}
}
triShell
void triShell(int tab[], int n) {

int i,j,temp,pas=0;

while(pas<n) pas=3*pas+1;

while(pas)
{
for(i=pas;i<n;i++)
{

temp=tab[i];

for(j=i;j>=pas && tab[j-pas]> temp ;j-=pas)


tab[j]=tab[j-pas];

tab[j]=temp;
}
pas/=3;
}
}

quickSort
void quickSort(int tab[],int bas,int haut)
{

if ( bas < haut)


{
int pivot = Partition(tab,bas,haut);

quickSort(tab,bas,pivot-1);

quickSort(tab,pivot+1,haut);
}
}
int Partition(int tab[],int bas,int haut)
{

int pivot = tab[haut],

i = bas-1;

for(int j=bas ; j < haut ; j++)


{
if( tab[j]<= pivot)
{
i++;

echanger(&tab[i],&tab[j]);

}
}

echanger(&tab[i+1],&tab[haut]);

return (i+1);

Binary Search
int chercherUneValeur(int tab[],int X,int n)
{
int inf=tab[0],
sup=tab[n];

while(inf<=sup)
{
int mil=(inf + sup)/2;
if(mil==X)
return mil;

else if (X>mil)

inf=mil+1;

else
sup=mil-1;
}

return -1;

}
rechercheSequentielle
int rechercheSequentielle(int tableau[], int taille, int element) {
for (int i = 0; i < taille; i++) {

if (tableau[i] == element) {

return i;
}
}

return -1;
}

Vous aimerez peut-être aussi