Tri et recherche

Algorithmes de tri

  1. Définition

  2. Le tri par sélection

  3. Le tri à bulles

  4. Le tri rapide

Définitions

  • Les tableaux (ensembles) permettent de stocker plusieurs éléments de même type au sein d'une seule entité.

  • Lorsque le type de ces éléments possède un ordre total, on peut donc les ranger en ordre croissant ou décroissant.

  • Trier un tableau <==> ranger les éléments d'un tableau en ordre croissant ou décroissant.

  • Il existe plusieurs méthodes de tri qui se différencient par leur complexité d'exécution et leur complexité de compréhension pour le programmeur.

  • Tous les algorithmes de tri utilisent une méthode qui permet d'échanger (de permuter) la valeur de deux variables.

En Algorithmique :

temp <- a ; a <- b ; b <- temp ;

En Python :

a,b = b,a ;

Par la suite, nous utiliserons la notation : echanger(a,b)

Tri par sélection

Tri par sélection <==> tri par minimum

Pour une place donnée, on sélectionne l'élément qui doit y être positionné.

Si on parcourt le tableau de gauche à droite, on positionne à chaque fois le plus petit élément qui se trouve dans le sous tableau droit.

Trier le sous-tableau t[i..nbElem]

Trouver le plus petit élément (valeur et position).

Echanger l'élément à l'indice i et le plus petit élément.

Continuer, en triant le sous-tableau t[i+1..nbElem].

tri de [101, 115, 30, 63, 47, 20]

  • Étape 1 : [20, 115, 30, 63, 47, 101]

  • Étape 2 : [20, 30, 115, 63, 47, 101]

  • Étape 3 : [20, 30, 47, 63, 115, 101]

  • Étape 4 : [20, 30, 47, 63, 115, 101]

  • Résultat : [20, 30, 47, 63, 101, 115]

-> Besoin d'une fonction qui trouve le minimum (valeur et position du plus petit élément)

Fonction indiceMin

  • En Algorithmique

fonction indiceMin(Entier t : tab[1..MAX], Entier deb, Entier nbElem) retourne Entier

  i, indiceCherche : Entier ;

Début

  indiceCherche <- deb ;

  Pour i de deb+1 à nbElem faire

    si t[i] < t[indiceCherche] alors indiceCherche <- i ;

  retourne(indiceCherche) ;

Fin.

  • En Python

def indiceMin(t):

... return(t.index(min(t))

Sous-programme de tri par sélection

  • En Algorithmique

procédure triParSelection(Entier t : tab[1..MAX], Entier nbElem)

  i, indice : Entier ;

Début

  Pour i de 1 à nbElem faire

  début

    indice <- indiceMin(t, i, nbElem) ;

    si i ≠ indice alors echanger(t[i],t[indice]) ; -- temp <- a ; a <- b ; b <- temp ;

  fin ;

Fin.

  • En Python

A faire !

Tri à bulle

Sélectionner le minimum du tableau :

  • en parcourant le tableau du début à la fin,

  • ET en échangeant tout couple d'éléments consécutifs non ordonnés.

tri de [101, 115, 30, 63, 47, 20]

  • Étape 1

[101, 115, 30, 63, 47, 20]

[101, 115, 30, 63, 47, 20]

[101, 30, 115, 63, 47, 20]

[101, 30, 63, 115, 47, 20]

[101, 30, 63, 47, 115, 20]

[101, 30, 63, 47, 20, 115]

  • Étape 2

[101, 30, 63, 47, 20, 115]

[30, 101, 63, 47, 20, 115]

[30, 63, 101, 47, 20, 115]

[30, 63, 47, 101, 20, 115]

[30, 63, 47, 20, 101, 115]

  • Étape 3

[30, 63, 47, 20, 101, 115]

[30, 63, 47, 20, 101, 115]

[30, 47, 63, 20, 101, 115]

[30, 47, 20, 63, 101, 115]

  • Étape 4

[30, 47, 20, 63, 101, 115]

[30, 47, 20, 63, 101, 115]

[30, 20, 47, 63, 101, 115]

  • Étape 5

[30, 20, 47, 63, 101, 115]

[20, 30, 47, 63, 101, 115]

  • Résultat : [20, 30, 47, 63, 101, 115]

Sous-programme de tri à bulle

  • En Algorithmique

procédure triABulle(Entier t : tab[1..MAX], Entier nbElem)

  i : Entier ;

  echanges : Booléen <- VRAI ;

Début

  Tant que echanges faire

  début

    echanges <- FAUX ;

    Pour i de 1 à nbElem-1 faire

      si t[i] > t[i+1] alors

      début

        echanger(t[i],t[i+1]) ;

        echanges <- VRAI ;

      fin ;

    nbElem <- nbElem -1 ;

  fin ;

Fin.

  • En Python

A faire !

Tri rapide

  • Choisir un élément du tableau appelé pivot.

  • Ordonner les éléments du tableau par rapport au pivot.

  • Appeler récursivement le tri sur les sous-tableaux à gauche et à droite du pivot.

tri de [101, 115, 30, 63, 47, 20]

  • Étape 1

[101, 115, 30, 63, 47, 20]

[101, 115, 30, 63, 47, 20]

[101, 30, 115, 63, 47, 20]

[101, 30, 63, 115, 47, 20]

[101, 30, 63, 47, 115, 20]

[101, 30, 63, 47, 20, 115]

[20, 30, 63, 47, 101, 115]

  • Étape 2

[20, 30, 63, 47] 101 [115]

[20, 30, 63, 47] 101 115

[20, 30, 63, 47] 101 115

[20, 30, 63, 47] 101 115

  • Étape 3

20 [30, 63, 47] 101 115

20 [30, 63, 47] 101 115

20 [30, 63, 47] 101 115

  • Étape 4

20 30 [63, 47] 101 115

20 30 [63, 47] 101 115

20 30 [47, 63] 101 115

  • Étape 5 : 20 30 [47] 63 101 115

  • Résultat : 20 30 47 63 101 115

Sous-programme de tri rapide

  • En Algorithmique

procédure triRapide(Entier t : tab[1..MAX], Entier pivot, Entier nbElem)

  Entier q ;

Début

  Si (pivot < nbElem) alors

  début

    q <- partionner(t, pivot, nbElem) ;

    triRapide(t, pivot, q-1) ;

    triRapide(t, q+1, nbElem) ;

  fin ;

Fin.

  • En Python

A faire !

Sous-programme de partition

  • En Algorithmique

fonction partionner(Entier t : tab[1..MAX], Entier pivot, Entier nbElem) retourne Entier

  Entier val_pivot <- t[pivot] ;

  Entier q <- pivot ;

  Entier i ;

Début

  Pour i de pivot + 1 à nbElem faire

    Si t[i] < val_pivot alors

    début

      q <- q + 1 ;

      echanger(t[q],t[i]) ;

    fin ;

  echanger(t[q],t[pivot]) ;

  retourne(q) ;

Fin.

  • En Python

A faire !

Complexité

Tri par sélection

Recherche du minimum sur un tableau de taille  :

Donc :

Complexité :

Tri à bulle

Pire ( étapes) : lorsque le minimum se situe à la fin du tableau de taille et nombre de comparaisons :

Complexité (au pire et en moyenne) :

Tri rapide

Complexité (au pire) : si le tableau est déjà trié (ou presque)

Complexité (en moyenne) :

Illustrations

Algorithmes de recherche

  1. Recherche dans un tableau non trié (rappel TD)

  2. Recherche séquentielle dans un tableau trié

  3. Recherche dichotomique dans un tableau trié

Recherche dans un tableau non trié

  • En Algorithmique

fonction rechercheNonTrie (Eléments t : tab[0..MAX], Entier nbElem, Elément x) retourne Entier

  Entier i <- 0 ;

Début

  Tant que (i ≤ nbElem) et (t[i] ≠ x) faire

    i <- i+1 ;

  Si (i=nbElem+1) alors retourne(-1);

  retourne(i) ;

Fin.

  • En Python

A faire !

Recherche séquentielle dans un tableau trié

  • En Algorithmique

fonction rechercheSeqTrie (Eléments t : tab[0..MAX], Entier nbElem, Elément x) retourne Entier

  Entier i <- 0 ;

Début

  Tant que (i ≤ nbElem) et (t[i] < x) faire

    i <- i+1 ;

  Si (i=nbElem+1) ou (t[i]>x) alors retourne(-1);

  retourne(i) ;

Fin.

  • En Python

A faire !

Recherche dichotomique dans un tableau trié

  • En Algorithmique

fonction rechercheDicoTrie (Eléments t : tab[0..MAX], Entier nbElem, Elément x) retourne Entier

  Entier gauche <- 0 ;

  Entier droit <- nbElem ;

  Entier milieu ;

Début

  Tant que gauche ≤ droit faire

  début

    milieu <- (gauche+droit) div 2 ;

    Si (t[milieu]=x) alors retourne(milieu) ;

    Si (t[milieu]<x) alors gauche <- milieu + 1 ;

    Sinon droit <- milieu -1 ;

  fin ;

Fin.

  • En Python

A faire !

Recherche dichotomique de ‘G' dans le tableau trié suivant : ‘AAAAAAAACCGTTTT'

  • Étape 1 : AAAAAAAACCGTTTT

  • Étape 2 : AAAAAAAACCGTTTT

  • Étape 3 : AAAAAAAACCGTTTT

  • Étape 4 : AAAAAAAACCGTTTT

  • Résultat : ‘G' en position 10

AccueilProgrammation en Python > Tri et recherche< PrécédentSuivant >