Retour

Tri par sélection

Principe :

Trier le tableau de gauche à droite en insérant à chaque fois l'élément i+1 parmi les premiers éléments déjà triés.

Algorithme impératif

Text Only

VARIABLES
t : tableau d'entiers
i, min, j, n : nombre entier

TRI_SELECTION(t):
  DEBUT
  i←1
  TANT QUE i < longueur(t):   //boucle 1
    j←i+1
    min←i

    TANT QUE j<= longueur(t):   //boucle 2
        si t[j]<t[min]:
        min←j
      FIN SI
      j←j+1
    FIN TANT QUE
    SI min≠i :
      échanger t[i] et t[min]
    FIN SI
    i←i+1
  FIN TANT QUE
  FIN 

Implémentation en Python

🐍 Script Python

def Tri_Selection(t):
  i = 0
  while i < len(t):
    j = i + 1
    min = i
    while j < len(t):
      if t[j] < t[min]:
        min = j
      j = j + 1
    if min != i:
      t[i], t[min] = t[min], t[i]
    i = i + 1

Complexité

Pire cas : Quadratique	$$ O(n^2) $$
Moyenne : Quadratique	$$ O(n^2) $$
Meilleur cas : Quadratique	$$ O(n^2) $$