Tri par sélection

Invariant, O(n²), instable

← Retour au cours Tri

Algorithme complet

O(n²)

À chaque étape : minimum de la partie droite, puis échange.

for indice in range(nb-1)
Partie non triée
indice_min = indice
Candidat minimum
tableau[j] < tableau[indice_min]
Chercher à droite
Échange
Si indice_min ≠ indice
tri_selection.py 
def tri_selection(tableau):
    nb_elements = len(tableau)
    for indice in range(0, nb_elements - 1):
        indice_min = indice
        for suivant in range(indice + 1, nb_elements):
            if tableau[suivant] < tableau[indice_min]:
                indice_min = suivant
        if indice_min != indice:
            tableau[indice], tableau[indice_min] = (
                tableau[indice_min], tableau[indice]
            )

Analyse

instable

n(n−1)/2 comparaisons ; non stable si échange lointain.

Complexité
O(n²) même si déjà trié
Stabilité
Non : ex. [3a, 3b, 1]
Échanges
Au plus n−1

💻 Exemples de code

Exemple d'utilisation

exemple_tri_selection.py 
notes = [15, 3, 8, 1]
tri_selection(notes)
print(notes)   # [1, 3, 8, 15]

📋 Aide-mémoire

def tri_selection(tableau): : double boucle for.