Tri et recherche



Les algorithmes de recherche

Exercice 1: Chercher une valeur dans une liste non triée (Recherche séquentielle)

Fonction Python chercher(v,L) qui retourne True si une valeur v existe dans une liste L ou qui retourne False sinon, v et L sont passés en paramètre.

Exemple:

>>>L=[2,5,1,0,4]
>>>chercher(5,L)
True
>>>chercher(12,L)
False


Exercice 2: Recherche dichotomique – Recherche dans une liste triée –

Fonction recherche_dichotomique( v , L) qui retourne l’indice de l’élément recherché v si la valeur v existe dans la liste L, et -1 si v n’existe pas dans la liste L. la valeur v et la liste L sont passés en paramètres.

Une autre technique de recherche dans une liste triée est la recherche dichotomique au lieu de rechercher séquentielle (recherche linière – liste non triée -).

Principe:

On compare la valeur à chercher à la valeur qui se trouve au milieu de la liste.

  • Si c’est le même la valeur donc est trouvée
  • Sinon on recommence soit sur la première moitié si la valeur recherchée est plus petite que la valeur rangé au milieu de la table
  • Soit sur la deuxième moitié si la valeur recherchée est plus grande que la valeur rangé au milieu de la liste.

Exemple d’exécution:

>>> L =[ 2 , 3 , 6 , 12 , 23 , 30 ]
>>> recherche_dichotomique( 6 , L)
2
>>> recherche_dichotomique( 16 , L)
-1


Les algorithmes sur les liste triées


Exercice 3: Vérifier si une liste est triée

Fonction Python Est_trie( L ) qui retourne True si L est trié (soit en ordre croissant soit en ordre décroissant) et elle retourne False sinon.

Exemple:

>>> L=[22,15,8,7,1]
>>> Est_trie(L)
True
>>> L=[2,5,8,9,16]
>>> Est_trie(L)
True
>>> L=[22,150,8,7,1]
>>> Est_trie(L)
False
>>> L=[2,3,3,7,10]
>>> Est_trie(L)
True
>>> L=[8,5,5,3,1]
>>> Est_trie(L)
True


Exercice 4: Insérer un nombre dans une liste triée

Fonction Python inserer( n, L ) qui permet d’insérer  un nombre n dans une liste L triée en ordre croissant, n et L sont passés en paramètres.

Exemple:

>>>L=[ 1, 2, 6, 9]
>>>inserer(3,L)
[1, 2 , 3, 6, 9]


Les algorithmes des tris quadratique


Exercice 5: Tri par sélection

Fonction Python tri_par_selection( L ) qui retourne une liste L triée en utilisant l’algorithme de tri par sélection, L est une liste passée en paramètre.

Principe du tri par sélection (tri croissant):

Le principe du tri par sélection/échange (ou tri par extraction) est d’aller chercher le plus petit élément du tableau pour le mettre en premier, puis de repartir du second élément et d’aller chercher le plus petit élément du tableau pour le mettre en second, etc…

Au ième passage, on sélectionne donc l’élément ayant la plus petite valeur parmi les éléments {T[i]…T[n]} et on l’échange avec T[i]. tous les élément du tableau de T[0] à T[i-1] sont déjà triés.

Exemple d’exécution:

>>> L=[3 , 1 , 7 , 9 , 4 , 12 , 5]
>>> tri_par_selection( L )
[ 1 , 3 , 4 , 5 , 7 , 9 , 12 ]


Exercice 6: Tri par insertion

Fonction Python tri_par_insertion( L ) qui retourne une liste L triée en utilisant l’algorithme de tri par insertion, L est une liste passée en paramètre.

Principe du tri par insertion (Tri croissant)

A l’étape i

on considéré que la liste est divisée en deux parties (deux listes L1 et L2)

  • L1 de taille i déjà triée se compose des élément d’ indices de 0 à i-1
  • L2 de taille n-i pas encore triée se compose des éléments d’indices de i jusqu’à n-1

On insert ensuite l’élément L[ i ] dans la liste L1 qui est déjà trié.
La taille de la liste L1 augmente par 1 devient i+1 et celle de L2 diminue par 1 devient n-i-1.
On répéte la procédure juqu’à que  la taille de  L1=n et la taille de L2=0

Exemple d’exécution:

>>> L=[5 , 1 , 7 , 2 , 6 , 4 , 3]
>>> tri_par_insertion( L )
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]


Exercice 7: Tri à bulle

Fonction Python tri_a_bulle( L ) qui retourne une liste L triée en utilisant l’algorithme de tri à bulle, L est une liste passée en paramètre.

Principe du tri à bulle (tri croissant):

Le principe du tri bulle est de comparer deux à deux les éléments e1 et e2 consécutifs d’un tableau et d’effecteur une permutation si e1 > e2. On continue de trier jusqu’à ce qu’il n’y ait plus de permutation.

Voici les étapes pour trier L = [4, 2, 8, 1, 7, 5, 3, 6]

étape 1: [2, 4, 8, 1, 7, 5, 3, 6]
étape 2: [2, 4, 1, 8, 7, 5, 3, 6]
étape 3: [2, 4, 1, 7, 8, 5, 3, 6]
étape 4: [2, 4, 1, 7, 5, 8, 3, 6]
étape 5: [2, 4, 1, 7, 5, 3, 8, 6]
étape 6: [2, 4, 1, 7, 5, 3, 6, 8]
étape 7: [2, 1, 4, 7, 5, 3, 6, 8]
étape 8: [2, 1, 4, 5, 7, 3, 6, 8]
étape 9: [2, 1, 4, 5, 3, 7, 6, 8]
étape 10: [2, 1, 4, 5, 3, 6, 7, 8]
étape 11: [1, 2, 4, 5, 3, 6, 7, 8]
étape 12: [1, 2, 4, 3, 5, 6, 7, 8]
étape 13: [1, 2, 3, 4, 5, 6, 7, 8]

Exemple d’exécution:

>>> L=[4 , 2 , 1 , 8 , 7 , 5 , 3 , 6 ]
>>> Tri_bulle( L )
[1, 2, 3, 4, 5, 6, 7, 8]


Les algorithmes des tris quasi-linéaire ou rapide


Exercice 8: Tri par fusion

Fonction Python tri_fusion(L) qui permet de trier une liste L en utilisant l’algorithme de tri par fusion, L est une liste passée en paramètre.

Principe de Tri par fusion

Le principe du tri par fusion, comme le tri rapide, basé à nouveau d’un tri suivant le paradigme diviser pour régner dont le principe est le suivant:

  • On divise en deux moitiés la liste à trier.
  • On trie chacune d’entre elles.
  • On fusionne les deux moitiés obtenues pour reconstituer la liste triée.

Voici un exemple explicatif du tri par fusion sur la liste L=[ 8 , 2 , 5 , 4 , 9 , 6 , 1 , 7]:

Exemple d’exécution:

>>> L=[ 8 , 2 , 5 , 4 , 9 , 6 , 1 , 7]:
>>> tri_fusion( L )
[1, 2 , 4 , 5 , 6 , 7, 8 , 9]


Exercice 9: Tri Rapide – quicksort –

Fonction Python tri_rapide(L) qui permet de trier une liste L en utilisant l’algorithme de tri rapide (en anglais quicksort), L est une liste passée en paramètre.

Principe de Tri rapide

Le principe du tri rapide (en anglais quicksort) est de diviser (diviser pour régner) la liste en deux sous listes (deux partitionnement) telles que les éléments de la première soient inférieurs aux éléments de la seconde. On recommence jusqu’à avoir des sous-listes réduites à un seul élément.

Pour diviser la liste en deux sous-listes, on choisit une des valeurs de la liste comme pivot (ici le pivot est le dernier élément).On construit une sous-liste gauche avec les éléments dont la valeur est inférieure à celle du
pivot et une sous-liste droite avec les éléments supérieurs au pivot.

Comme on fait cette construction directement sur la liste qui représente la liste, la frontière entre les deux sous-listes donne la place définitive du pivot.

Exemple de fonctionnement: Tri rapide pour la liste  L=[ 3 , 5 , 2 , 1 , 8 , 9 , 7 , 4 ]

Ici on choisi le dernier élément comme pivot

 [ 3 , 2 , 1 ][ 4 ][5 , 8 , 9 , 7]  Le pivot=4 est bien placé à sa place définitive.

1 ][3 , 2][ 4 ][5, 8 , 9 , 7 ]   Le pivot=1 est bien placé à sa place définitive.

[ 1 ][ 2 ][ 3][ 4 ][5, 8, 9, 7]   Le pivot=2 est bien placé à sa place définitive.

[ 1 ][ 2 ][ 3][ 4 ][5, 8, 9, 7]   Le pivot=3 est bien placé à sa place définitive.

[ 1 ][ 2 ][ 3][4][5][7 ][8, 9]   Le pivot=7 est bien placé à sa place définitive.

[1][2][3 ][4 ] [5 ][7 ][8 , 9]   le pivot=5 est bien placé à sa place définitive.

[1][2][3][4 ][5 ][7 ][8 ][9 ]  le pivot=9 est bien placé à sa place définitive.

[1][2][3 ][4][5 ][7 ][8 ][9 ]  le pivot=8 est bien placé à sa place définitive.

Résultat finale la liste L est bien triée [ 1, 2, 3, 4, 5, 7, 8, 9]

Exemple d’exécution:

>>> L=[4 , 2 , 1 , 8 , 7 , 5 , 3 , 6 ]
>>> tri_rapide( L )
[1, 2, 3, 4, 5, 6, 7, 8]


Les algorithmes des tris linéaire

Exercice 10 : Tri par dénombrement

Une méthode de tri applicable à une situation particulière : le tri par dénombrement. Il s’agit de trier une suite de n nombres entiers dont les valeurs sont comprises entre 0 et k.

Le tri par dénombrement est un tri bien particulier il ne se base pas sur la comparaisons et il s’applique seulement sur les entiers naturels.

Si k n’est pas très grand on peut utiliser l’algorithme suivant :

  • Parcourir la liste L en créant une lise auxiliaire compte des fréquences des éléments de L(avec compte[i]= le nombre de fois où i apparaît dans le tableau)
  • Parcourir la liste L dans le sens croissant (pour un tri croissant), ou décroissant (pour un tri décroissant) en plaçant dans l’élément d’indice i compte[i] fois l’élément i.

Exemple :  L =  [ 7 , 1 , 3 , 1 , 2 , 4 , 5 , 7 , 2 , 4 , 3 ]

  • Etape 1 : compte = [ 0 ,   2 ,   2 ,   2 ,   2 ,   1 ,   0 ,   2]
  • Etape 2 : L = [ 1 ,   1 , 2 ,   2 ,   3 ,   3 ,   4 ,   4 ,   5 ,  7 ,   7 ]

Ecrire une fonction Python qui effectue le tri par dénombrement d’une liste de n entiers positifs ayant une valeur inférieure à k.


Exercice 11: Comparaison entre les tris: Insertion, sélection, à bulles, rapide, fusion et dénombrement

Programme Python (Comparaison entre les tris) qui compare la performance et la rapidité entre les tris déjà vus (Tri par sélection, par insertion,  à bulles, rapide, fusion et dénombrement) en calculant le temps d’exécution de chaque tri sur une liste générée aléatoirement de taille 1000.

N.B: Le tri par dénombrement est un tri bien particulier il s’applique seulement sur les entiers naturels.

Exemple d’exécution:


Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Résoudre : *
17 × 19 =