Les algorithmes de tri

Le tri par sélection

Le tri par sélection est celui qui utilise le concept le plus simple. Étant donné qu’il existe un algorithme qui permet de renvoyer la valeur la plus petite d’un tableau, on peut l’appliquer systématiquement pour reconstruire un tableau trié. En d’autres termes, à chaque case du tableau que l’on souhaite trier, on effectue une recherche dans la partie de droite pour retrouver l’élément le plus petit. Une fois trouvé, on échange les valeurs.

PROCÉDURE TRI_SELECT(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, min, swap: ENTIER
    POUR i DE 0 À N-2:
        min <- i

        POUR j DE i À N-1:
            SI t[j] < t[min], ALORS
                min = j
            FIN SI
        FIN POUR

        swap <- t[min]
        t[min] <- t[i]
        t[i] <- swap

    FIN POUR
FIN PROCÉDURE

def select(tableau, size):
    tmp = 0

    for i in range(0, size-1):
        min = i
        for j in range(i, size):
            if tableau[j] < tableau[min]:
                min = j

        tmp = tableau[i]
        tableau[i] = tableau[min]
        tableau[min] = tmp

void sort_select(int tableau[], int size) {
  int min, tmp;

  for(int i=0; i<size; i++) {
    min = i;

    for(int j=i; j<size; j++) {
      if( tableau[j] < tableau[min] )
        min = j;
    }

    tmp = tableau[i];
    tableau[i] = tableau[min];
    tableau[min] = tmp;
  }
}

Le tri à bulles

Il consiste à comparer répétitivement les éléments consécutifs d’un tableau, et à les permuter lorsqu’ils sont mal triés. Il doit son nom au fait qu’il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d’air qui remonteraient rapidement à la surface d’un liquide.

PROCÉDURE TRI_A_BULLES(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, swap: ENTIER
    POUR i DE 0 À N-1
        POUR j DE N-2 À i, PAR PAS DE -1:
            SI t[j+1] < t[j]:
                swap <- t[j+1]
                t[j+1] <- t[j]
                t[j] <- swap
            FIN SI
        FIN POUR
    FIN POUR
FIN PROCÉDURE

def bubble(tableau, size):
    for i in range(0, size):
        # L'erreur commune est d'écrire range(size-2, i, -1), mais la valeur i ne sera jamais atteinte.
        for j in range(size-2, i-1, -1):
            if tableau[j+1] < tableau[j]:
                tmp = tableau[j+1]
                tableau[j+1] = tableau[j]
                tableau[j] = tmp

void sort_bubble(int tableau[], int size) {
  int tmp;

  for(int i=0; i<size; i++) {

    for(int j=size-2; j>=i; j--) {

      if( tableau[j] > tableau[j+1] ) {
        tmp = tableau[j];
        tableau[j] = tableau[j+1];
        tableau[j+1] = tmp;
      }
    }
  }
}

PROCÉDURE TRI_A_BULLES_FASTER(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, swap: ENTIER
    VARIABLE trié: BOOLÉEN

    trié <- Faux
    TANT QUE trié != Vrai ET 0 < n -1

        trié <- Vrai
        POUR j DE N-2 À i, PAR PAS DE -1:
            SI t[j+1] < t[j]:
                swap <- t[j+1]
                t[j+1] <- t[j]
                t[j] <- swap
                trié <- Faux
            FIN SI
        FIN POUR

        i <- i+1
    FIN TANT QUE
FIN PROCÉDURE

def bubble_skip(tableau, size):
    i = 0
    sort = False
    while sort is False and 0 < size-1:
        sort = True
        # L'erreur commune est d'écrire range(size-2, i, -1), mais la valeur i ne sera jamais atteinte.
        for j in range(size - 2, i-1, -1):
            if tableau[j + 1] < tableau[j]:
                tmp = tableau[j+1]
                tableau[j+1] = tableau[j]
                tableau[j] = tmp
                sort = False
        i = i + 1

void sort_bubble_fast(int tableau[], int size) {
  int tmp;
  bool sorted = false;
  
  int i = 0;
  while( i < size && sorted == false ) {

    sorted = true;
    for(int j=size-2; j>=i; j--) {

      if( tableau[j] > tableau[j+1] ) {
        tmp = tableau[j];
        tableau[j] = tableau[j+1];
        tableau[j+1] = tmp;
        sorted = false;
      }
    }

    i++;
  }
}

Le tri par insertion

Le tri par insertion est considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. La plupart des personnes l’utilisent naturellement pour trier des cartes à jouer.

PROCÉDURE TRI_INSERT(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, swap: ENTIER

    POUR i DE 1 À N-1:
        j <- i 
        TANT QUE j > 0 AND a[j-1] > a[j]:
            swap <- a[j]
            a[j] <- a[j-1]
            a[j-1] <- swap

            j <- j-1
        FIN TANT QUE
    FIN POUR
FIN PROCÉDURE

def insert(tableau, size):
    for i in range(1, size):
        j = i
        while j > 0 and tableau[j-1] > tableau[j]:
            tmp = tableau[j-1]
            tableau[j-1] = tableau[j]
            tableau[j] = tmp
            j = j -1

void sort_insert(int tableau[], int size) {
  int tmp, j;
  
  for(int i=0; i<size; i++) {
    j = i;

    while( j > 0 && tableau[j-1] > tableau[j] ) {
      tmp = tableau[j];
      tableau[j] = tableau[j-1];
      tableau[j-1] = tmp;
      j--;
    }
  }
}

Le tri rapide

Il existe des familles de tri, plus rapide, mais aussi plus complexe à implémenter. L’un de ces algorithmes est celui de quicksort où l’idée est de diviser pour mieux régner. Cependant, cette famille n’est pas la plus rapide lorsque les données sont déjà triées sauf un seul élément. Il faut préférer le tri par sélection dans ce cas-là. L’idée est de fixer arbitrairement une valeur pivot, et de déplacer les valeurs à droite si elles sont plus grandes que le pivot ou à gauche dans le cas contraire. Une fois fait, il faut rééxécuter ce même algorithme sur ces deux nouvelles parties des tableaux. Il s’agit ici d’un algorithme récursif.

PROCÉDURE TRI_RAPIDE(t: TABLEAU D'ENTIERS, g: ENTIER, d: ENTIER)
    VARIABLES i, j, p, swap: ENTIER
    i <- g
    j <- d
    p <- t[j]

    TANT QUE i < j:
        TANT QUE t[i] < p:
            i <- i+1
        FIN TANT QUE
        TANT QUE t[j] > p:
            j <- j-1
        FIN TANT QUE

        SI i <= j, ALORS:
            swap <- t[i]
            t[i] <- t[j]
            t[j] <- swap

            i <- i+1
            j <- j-1
        FIN SI
    FIN TANT QUE

    SI g < j, ALORS:
        TRI_RAPIDE(t, g, j)
    FIN SI

    SI i < d, ALORS:
        TRI_RAPIDE(t, i, d)
    FIN SI
FIN PROCÉDURE

def quick(tableau: SortableArray, size: int):
    def run(g: int, d: int):
        i = g
        j = d
        # Techniquement, le pivot peut être n'importe quel indice compris entre i et j
        # Il est commun de voir i, j
        p = j

        while i < j:
            while tableau[i] < tableau[p]:
                i = i + 1
            while tableau[j] > tableau[p]:
                j = j - 1  # L'erreur commune est d'écrire +1

            if i <= j: # L'erreur commune est d'écrire i<j
                tmp = tableau[i]
                tableau[i] = tableau[j]
                tableau[j] = tmp
                i = i + 1
                j = j - 1

        if g < j:
            run(g, j)
        if i < d:
            run(i, d)

    run(0, size-1)

void run_quicksort(int tableau[], int left, int right) {
  int tmp;
  int i = left;
  int j = right;
  int pivot = tableau[(i+j)/2];

  while( i < j ) {

    while( tableau[i] < pivot )
      i++;
    while( tableau[j] > pivot )
      j--;

    if( i <= j) {
      tmp = tableau[i];
      tableau[i] = tableau[j];
      tableau[j] = tmp;
      
      i++;
      j--;
    }
  }

  if( left < j )
    run_quicksort(tableau, left, j);
  if ( i < right )
    run_quicksort(tableau, i, right);
    
}
void sort_quick(int tableau[], int size) {
  run_quicksort(tableau, 0, size);
}

La complexité des tris

Bien que QUICKSORT soit le plus rapide, il existe cependant un cas de figure théorique où l’algorithme est au pire cas en complexité quadratique. Toutefois, malgré ce désavantage, c’est en pratique un des tris les plus rapides, et donc l’un des plus utilisés. Par contre, il restera plus lent que le tri par insertion dans le cas où le tableau est pratiquement déjà entièrement trié.

Il est d’ailleurs possible de combiner deux algorithmes ensembles pour éviter le pire cas. Par exemple, on peut utiliser le tri rapide lorsque le tableau est très grand, mais une fois que l’intervalle est suffisamment petit, on peut utiliser un tri par insertion. C’est exactement le fonctionnement de Introsort.