Texte

Complexité des tris simples

Complexité du tri par sélection

Soit une solution Python du tri par sélection :

def tri_selection(s):                                            # O(n^2)
   """Trie  la liste s par sélection."""
   n = len(s)                                                    # O(1)
   for i in range(n-1):                                          # O(n^2) (O(n) itérations)
      # recherche du min dans s[i..n]
      min = i # min = indice du min provisoire                     # O(1)
      for j in range(i+1,n):                                       # O(n) (O(n) itérations)
        if  s[j][0] < s[min][0]:                                      # O(1)
           min = j                                                       # O(1)
      # placement du ième élément: échange s[i]<->s[min]
      s[min],s[i] =  s[i],s[min]                                   # O(1)

où l'on suppose ici aussi, le vecteur s composé de couples (clé, information satellite).

Pour calculer la complexité maximale du tri par sélection décomposons l'algorithme sous forme d'arbre en suivant sa structure; ceci est donné en figure suivante:

Décomposition du tri par sélection

En supposant que toutes les instructions et les traitements de passages de paramètres interviennent dans ce calcul, en suivant les règles pour calculer cette complexité, nous obtenons :

• 1, 5, 8, 11 et 13 , sont en \(O(1)\)
• le if (10-11) est en \(O(1)\)
• le for (9-11) imbriqué est en \(O(n-i)\) et peut être borné par \(O(n)\)
• le for global (6-13) est en \(O(n^2)\)
• la procédure tri_selection (1-13) est en \(O(n^2)\)

Ce calcul peut être raffiné mais les résultats restent en \(O(n^2)\).

Complexité du tri par insertion

En analysant l'algorithme de tri par insertion, on peut voir que sa complexité maximale est également en \(O(n^2)\). On peut voir que la complexité minimale est rencontrée dans le cas où la liste est déjà triée et vaut \(O(n)\)

Complexité du tri par échange ou tri Bulle

Pour le tri par échangé, également appelé, tri bulle, la complexité maximale est également en \(O(n^2)\). Ici, la complexité minimale est aussi en \(O(n^2)\).

Complexité du tri par énumération

Soit une solution Python du tri par énumartion où l'on suppose les valeurs possibles en \(0\) et \(m - 1\) :

m = 5

def tri_enumeration(s):
   """Trie les n premières composantes de la liste s par énumération."""
   n = len(s)                                      # O(1)
   w = [0]*n                                       # O(n)
   count = [-1]+[0]*(m-1)                          # O(m)

   # 1 Comptage
   for j in range(n):                              # O(n) (O(n) itérations)
      count[s[j][0]] +=1                             # O(1)

   # 2 Cumul des compteurs
   for i in range(1,m):                            # O(m) (O(m) itérations)
     count[i] += count[i-1]                          # O(1)

   # 3 Placement des éléments dans w
   for j in range(n-1,-1,-1):                      # O(n) (O(n) itérations)
     w[count[s[j][0]]] = s[j]                        # O(1)
     count[s[j][0]] -= 1                             # O(1)

   # 4 Recopiage de w dans s
   s[:] = w                                        # O(n)

Si \(m < n\), la complexité moyenne et maximale de ce tri est en \(O(n)\) ce qui est remarquable.