Algorithmes et Structures de Données

Tri par sélection

L’algorithme de tri par sélection fait partie des méthodes de tri les plus intuitives. Il consiste à trouver l’élément minimal dans le tableau et à le placer en première position. Puis, il passe à la recherche du prochain élément minimal dans la partie restante du tableau et répète ce processus jusqu’à arriver à la fin du tableau.
a = [...]
for i in range(len(a)):                  # Nous devons placer l’élément minimal de a[i:] dans a[i]
    min_idx = i                          # Indice de l’élément minimal
    for j in range(i + 1, len(a)):       # Trouver l’indice de l’élément minimal
        if a[j] < a[min_idx]:            # Si nous trouvons un élément plus petit
            min_idx = j                  # Mettre à jour l’indice de l’élément minimal
    a[i], a[min_idx] = a[min_idx], a[i]  # Échanger a[i] et a[min_idx]
print(a)
À chaque itération, on sélectionne l’élément le plus petit du sous-tableau restant et on l’échange avec l’élément courant en se basant sur leur indice. Dans le cas où l’élément courant est déjà le plus petit, l’échange se fera avec lui-même et n’apportera aucun changement au tableau.
 
L’algorithme de tri par sélection recherche donc l’élément minimal et échange l’indice courant avec celui-ci. Concrètement, à chaque itération, il parcourt la totalité de la partie restante du tableau pour trouver la valeur minimale (la fonction min parcourt les éléments un par un pour repérer la plus petite valeur). Par conséquent, l’algorithme effectue n itérations, qui chacune comptent environ n opérations, conduisant à un temps d’exécution total de .
Examinons son fonctionnement sur quelques tableaux :
[4, 1, -1, 0, 2, 8]
  1. i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]
  1. i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 4, 1, 2, 8]
  1. i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 1, 4, 2, 8]
  1. i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
  1. i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ swap ⇒ [-7, 5, 1, -1, -2, 10]
  1. i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, 1, -1, 5, 10]
  1. i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [1, 2, 3, 4, 5]

Défi

Étant donné n entiers, triez-les par ordre croissant en utilisant le tri par sélection.

Entrée

La première ligne de l’entrée contient un seul entier n (1 ≤ n ≤ 1000) qui représente le nombre d’éléments du tableau.
La ligne suivante contient n entiers séparés par des espaces : ().

Sortie

Le programme doit imprimer le tableau d’entrée trié en ordre croissant.

Exemples

Input
Output
5 5 5 3 2 3
2 3 3 5 5

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue