Tri par selection

Le tri par selection fonctionne comme quand tu tries des cartes a jouer dans ta main. A chaque étape, tu cherches la plus petite carte dans le paquet non trie, et tu la places au debut.

Concretement :
- Tu parcours toute la liste pour trouver le minimum
- Tu le mets en première position (en l'echangeant avec l'élément qui y est)
- Tu recommences avec le reste de la liste (a partir de la deuxieme position)

C'est aussi O(n²), mais le tri par selection fait moins d'echanges que le tri a bulles.

Écris une fonction tri_selection(lst) qui trie une liste en place.

Exemple :
lst = [64, 25, 12, 22, 11]
tri_selection(lst)
Apres l'appel, lst vaut [11, 12, 22, 25, 64]

Tests (2/4)

Tri basique

lst = [64, 25, 12, 22, 11]
tri_selection(lst)
assert lst == [11, 12, 22, 25, 64]

Liste a 1 élément

lst = [42]
tri_selection(lst)
assert lst == [42]

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def tri_selection(lst):
    n = len(lst)
    for i in range(n):
        idx_min = i
        for j in range(i + 1, n):
            if lst[j] < lst[idx_min]:
                idx_min = j
        lst[i], lst[idx_min] = lst[idx_min], lst[i]

← Tri a bulles Tri par insertion →

solution.py

Bravo!

Tri par selection

Tests (2/4)

Indices (3 disponibles)

Solution officielle