Scribd
Importer
6 vues3 pages

Méthodes de Tri en Informatique

Le document présente des méthodes de tri classiques en informatique, notamment le tri par sélection et le tri à bulles, en expliquant leurs principes et en fournissant des exemples de code. Il aborde également la recherche séquentielle, qui consiste à parcourir un tableau pour trouver un élément, ainsi que la recherche dichotomique, bien que cette dernière ne soit pas développée. Ces algorithmes sont essentiels pour diverses applications, comme le classement et l'organisation de données.

Transféré par

samira
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd
6 vues3 pages

Méthodes de Tri en Informatique

Le document présente des méthodes de tri classiques en informatique, notamment le tri par sélection et le tri à bulles, en expliquant leurs principes et en fournissant des exemples de code. Il aborde également la recherche séquentielle, qui consiste à parcourir un tableau pour trouver un élément, ainsi que la recherche dichotomique, bien que cette dernière ne soit pas développée. Ces algorithmes sont essentiels pour diverses applications, comme le classement et l'organisation de données.

Transféré par

samira
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd

LES TRAITEMENTS AVANCES

Le problème de tri est un classique de l'informatique ; les méthodes de tri sont utilisées dans
différentes applications. Par exemple :
- classer les élèves par ordre alphabétique ou par ordre de mérite
- mettre en ordre un dictionnaire
- trier l'index d'un livre

I) TRI PAR SELECTION :

Principe :
- Commencer à chercher l’indice du minimum de la liste L ;
- Permuter le 1er élément de la liste avec l’élément minimum trouvé ;
- Chercher l’indice du minimum des éléments de la sous liste L[1 :] et le permuter
avec le 2ème élément…
- Continuer ce principe jusqu’à ce que la liste devienne triée.
D’une manière générale, on échange l’élément à la position i avec le minimum de la sous
liste L[i+1:]. L’algorithme se termine au bout de n-1 boucles quand on a trouvé les n-1
minimums successifs. Exemple : L=[4,5,1,-6,2]
- Etape N°1 : le minimum de L est -6, on le permute avec 4 : L=[-6,5,1,4,2] ;
- Etape N°2 : le minimum de [5,1,4,2] est 1, on le permute avec 5 : L=[-6,1, 5,4,2]
- Etape N°3 : le minimum de [5,4,2] est 2, on le permute avec 5 : L=[-6,1,2,4,5]
- Etape N°4 : le minimum de [4,5] est 4, il est à sa bonne place.

def tri_selection(T,N):
for i in range(N):
min = i
for j in range(i+1, N):
if T[min] > T[j]:
min = j
tmp = T[i]
T[i] = T[min]
T[min] = tmp

II) TRI A BULLES


Principe : Parcourir la liste en comparant à chaque fois deux éléments successifs(L[i] et L[i+1]), si
l’ordre croissant n’est pas respecté (L[i]>L[i+1]) alors on permute les deux éléments. On répète le
parcours de la liste jusqu’à ce qu’on ne permute plus. On est sûre d’obtenir une liste triée au bout
de n-1 parcours mais parfois le processus s’arrête un peu plus tôt.

1
def tri_bulle(T,N):
for i in range(N):
for j in range(0, N-i-1):
if T[j] > T[j+1] :
tmp = T[j]
T[j] = T[j+1]
T[j+1] = tmp

III) RECHERCHE SEQUENTIELLE :


Principe : La recherche séquentielle consiste à parcourir un tableau d'éléments dans l'ordre
de ses indices jusqu'à ce qu'un élément recherché soit trouvé ou bien que la fin du tableau soit
atteinte et l’élément recherché est alors inexistant

IV) RECHERCHE DICHOTOMIE :


Principe :

2
3

Vous aimerez peut-être aussi