Les algorithmes de tris sont dans la section Algorithmique.

• Contenus : tris par insertion, par sélection
• Capacités attendus : écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.
• Commentaires : la terminaison de ces algorithmes est à justifier. On montre que leur coût est quadratique dans le pire cas.

Tri par insertion

Un cas concret

Commençons par trier à la main un jeu de carte !

Cinq cartes vous ont été distribuées et vous les retournez une à une pour les ranger par ordre croissant dans votre main.

La première carte retournée est :

La deuxième carte retournée est :

Vous mettez cette carte à droite en tant que plus grosse ; votre main triée est alors :

La troisième carte retournée est :

Vous insérez cette carte entre le 5 et le 10 ; votre main triée est alors :

La quatrième carte retournée est :

Vous insérez cette carte entre le 8 et le 10 ; votre main triée est alors :

La dernière carte retournée est :

Vous insérez cette carte au debut ; votre main triée est alors :

Ainsi la liste des valeurs des cinq cartes obtenues [5, 10, 8, 9, 2] a été triée par des insertions successives en [2, 5, 8 , 9, 10] :

Tri par insertion

Ce tri correspond au tri de cartes généralisé avec une liste de valeurs.

On considère les éléments de la liste un par un (comme pour les cartes) :

• le premier élément de la liste forme une liste triée à un seul élément,

• le deuxième élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais une liste triée à deux éléments,

• le troisième élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais une liste triée à trois éléments,

• ...

• le dernier élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais complètement trié la liste initiale.

Voici le pseudo-code en langage naturel de ce tri :

tri_insertion(liste L indexée de 0 à n-1)
	Pour i allant de 1 à n-1 faire
		placer l'élément L[i] dans la liste déjà classée L[0:i-1] 
	retourner la liste L

Pour placer au bon endroit l'élément L[i], il suffit de permuter cet élément avec le précédent dans la liste triée tant que cet élément précédent est plus grand (et qu'il existe !).

Voici donc le tri par insertion écrit en langage Python :

def tri_insertion(lst: list) -> list:
    for i in range(1, len(lst)):
        elt = lst[i]
        j = i
        while j > 0 and elt < lst[j-1]:
            lst[j] = lst[j-1]
            j -= 1
        lst[j] = elt
    return lst

Pour visualiser comment cet algorithme trie une liste quelconque, accéder à un site Web en cliquant sur l'image ci-dessous :

Un fois accédé.e à ce site, cliquer sur Trier pour lancer l'application.

Voici ci-dessous une animation gif qui illustre où positionner le nombre 1 en position d'index 6 de la liste [1,3,3,4,6,8,1,2,6,4,9,1] sachant que les 6 premiers nombres [1,3,3,4,6,8] sont déja triés :

Si vous n'avez pas un accès direct à Python, il est possible de vous servir du Trinket accessible avec ce lien pour saisir et tester temporairement votre code.
Ah ! Les joies d'un bac à sable !

exercice de renforcement

Complexité

Vous allez désormais calculer la complexité de l'algorithme de tri par insertion, rappelé ci-dessous, dans le pire des cas, c'est à dire dans le cas où toutes les valeurs sont triées dans l'ordre décroissant.

def tri_insertion(lst: list) -> list:
    for i in range(1, len(lst)):			# le premier élément forme seul une liste classée 
        elt = lst[i] 						# élément à classer
        j = i
        while j > 0 and elt < lst[j-1]:	# permutation avec le précédent s'il est plus grand
            lst[j] = lst[j-1]     
            j -= 1 
        lst[j] = elt						# placement au bon endroit
    return lst

Socrative sur la complexité.

Le tri par insertion est un tri qui semble naturel et facile à implémenter.

Son coût dans le cas le pire est quadratique. Toutefois, il offre de bons résultats sur des listes de peu d'éléments ou partiellement triées.

Exercices

def tri_1(liste):
    n = len(liste)
    i = 1
    while i < n:
        x = liste[i]
        j = i
        while liste[j-1] > x :
            liste[j] = liste[j-1]
            j = j-1
        liste[j] = x
        i = i+1
    return liste    

def tri_2(liste):
    for i in range(1, len(liste)):
        x = liste[i]
        j = i
        while j > 0 and liste[j-1] > x:
            liste[j] = liste[j-1]
        liste[j] = x
    return liste    

def tri_3(liste):
    i = 1
    for i in range(1, len(liste)):
        x = liste[i]
        for j in range(i, len(liste)):
            if liste[j-1] > x:
                liste[j] = liste[j-1]
        liste[j] = x
    return liste    

def tri_4(liste):
    n = len(liste)
    i = 1
    while i < n:
        x = liste[i]
        j = i
        while j> 0 and liste[j-1] > x:    
            j = j-1
            liste[j] = liste[j-1]
        liste[j] = x
        i = i+1
    return liste

lst = ['poire', 'pomme', 'abricot', 'kiwi', 'orange', 'noix', 'noisette', 'cerise', 'brugnon', 'nectarine', 'prune', 'groseille', 'framboise']

exercice de renforcement

def mystere(tab, valeur):
    """
    : param tab (list)  liste d'entiers triée par ordre croissant
    : param valeur (int) - entier
    : return (list)
    Sortie : ......................................................................................................
    """
    return [x for x in tab if x < valeur] + [valeur] + [x for x in tab if x >= valeur]

exercice de renforcement

Tri par sélection

Un cas concret

Recommençons par trier un jeu de carte à la main !

Cinq cartes vous ont été distribuées et vous les avez toutes dans un ordre quelconque dans votre main.

Supposons que les cartes en main soient :

Pour trier les cartes, l'idée est de :

1. balayer l'ensemble des cartes non encore triées afin d'y repérer la plus petite.

2. Cette plus petite carte restante est alors placée en première position des cartes pas encore triées.

Mise en œuvre de la démarche sur l'ensemble des cinq cartes :

Aucune carte n'a déjà été triée. Parmi les 5 de l'ensemble, la plus petite est le 2 (de carreau) :

Cette carte de valeur minimale est placée en première position par une permutation de deux cartes, d'où la nouvelle configuration :

Le 2 est déjà bien placé. Parmi les 4 cartes restantes, la plus petite est le 5 (de cœur) : par hasard, il est déjà bien placé :

Deux cartes sont déjà bien placées. Parmi les 3 cartes restantes, la plus petite est le 8 (de carreau) :

Cette carte restante de valeur minimale est placée en première position des cartes restantes par une permutation de deux cartes, d'où la nouvelle configuration :

Trois cartes sont déjà bien palcés. Parmi les 2 cartes restantes, la plus petite est le 9 (de pique) :

Cette carte restante de valeur minimale est placée en première position des cartes restantes par une permutation de deux cartes, d'où la nouvelle configuration :

La dernière carte restante non triée est forcément la plus grande de toutes : aucun nouveau changement n'est nécessaire pour obtenir finalement la liste entièrement triée :

Tri par sélection

On considère les éléments de la liste un par un (comme pour les cartes) :

• le plus petit élément de la liste est mis en première position par permutation ; on a désormais un début de liste triée à un élément,

• le deuxième plus petit élément de la liste est rangé en seconde position par permutation ; on a désormais un début de liste triée à deux éléments,

• ...

• l'avant dernier plus petit élément de la liste est rangé en avant-dernière position par permutation : on a désormais complètement trié la liste initiale.

Voici le pseudo-code en langage naturel de ce tri :

tri_selection(liste L indexée de 0 à n-1)
	Pour i allant de 0 à n-2 faire
		trouver le plus petit élement L[j] de la liste entre i et n-1
		échanger les éléments L[i] et L[j] 
	retourner la liste L

Deux fonctions seront utiles pour écrire en python cet algorithme :

• la fonction get_position_min qui renvoie l'index du minimum d'une liste entre un index nommé depart et son dernier terme. Cette liste et l'index depart sont entrés comme paramètres.

• la fonction echanger qui permute deux éléments d'une liste extraite entrée comme paramètre, les deux index de ces éléments étant aussi entés comme paramètres.

def get_position_min(lst: list, depart: int) -> int:
    pos = depart					# pos stocke la position du minimum : lst[pos] sera donc le minimum trouvé
    i = pos + 1
    while i < len(lst):
        .......................... 	# ligne 5
        .......................... 	# ligne 6
        i += 1
    return pos 

def echanger(lst: list, i1: int, i2: int) -> None:
    a = ...................... 	# ligne 2
    .......................... 	# ligne 3
    .......................... 	# ligne 4
    return None 

Pour visualiser comment cet algorithme trie une liste quelconque, accéder à un site Web en cliquant sur l'image ci-dessous :

Un fois accédé.e à ce site, cliquer sur Trier pour lancer l'application.

Voici ci-contre une animation qui permet de visualiser le tri par sélection :

• les nombres sur fond jaune sont déjà triés,

• le nombre sur fond rouge est le minimum de ceux déjà étudiés parmi les nombres encore à trier,

• le nombre sur fond bleu est celui en cours d'étude (celui dont la valeur sera comparée au minimum actuel sur fond rouge),

• la double flèche noire signifie qu'il y a permutation des valeurs ciblées.

Complexité

Vous allez désormais calculer la complexité de l'algorithme de tri par sélection, rappelé ci-dessous, dans le pire des cas, c'est à dire dans le cas où toutes les valeurs sont triées dans l'ordre décroissant.

# Les deux fonctions étudiées précédemment :

# la fonction de recherche de l'index du minimum :
def positionner(lst: list, depart: int) -> int:
    pos = depart					# pos stocke la position du minimum : lst[pos] sera donc le minimum trouvé	
    i= pos+1
    while i < len(lst):
        if lst[i] < lst[pos]:	# cas où une valeur plus petite que le minimum est trouvée
            pos = i
        i += 1
    return pos 						# index du minimum de la liste entre depart et dernière valeur
    
# la procédure d'échange de deux termes :
def permuter(lst: list, i1: int, i2: int) -> None:
    a = lst[i1] 				# utilisation d'une variable temporaire pour stocker la valeur qui sera écrasée par remplacement par la seconde valeur
    lst[i1] = lst[i2]
    lst[i2] = a
    return None 					# aucun retour : la permutation a eu lieu sur la liste lst qui est donc modifiée.

# Tri par sélection
    def tri_selection(lst: list) -> None:
        for i in range(len(lst)-1):					# on balaie toute la liste
            pos = positionner(lst, depart=i)		# on cherche le minimum parmi les termes non encore triés
            if pos != i:							# cas où le minimum n'est pas placé juste après la partie déjà triée
                permuter(lst, i1=i, i2=pos)
    return None										# aucun retour : la permutation a eu lieu sur la liste lst qui est donc modifiée.	

On considère que :

• chaque affectation correspond à une opération,

• chaque comparaison correspond à une opération,

• chaque obtention du terme d'une liste à partir de son index correspond à une opération.

QCM sur Socrative pour déterminer la complexité de la procédure de tri par sélection.

Exercices

def tri_1(liste):
    for i in range(len(liste)):
        min = i
        for j in range(i+1, len(liste)):
            if liste[min] > liste[j]:
                min = j
        liste[i] = liste[min]
        liste[min] = liste[i]
    return liste			

def tri_2(liste):
    i = 0
    while i < len(liste):
        min = i
        for j in range(i+1, len(liste)):
            if liste[min] > liste[j]:
                min = j
        _temp = liste[i]
        liste[i] = liste[min]
        liste[min] = _temp
    return liste			

def tri_3(liste):
    i = 0
    while i < len(liste):
        min = i
        for j in range(i+1, len(liste)):
            if liste[min] > liste[j]:
                min = j
                _temp = liste[i]
                liste[i] = liste[min]
                liste[min] = _temp
        i = i+1
    return liste

def tri_4(liste):
    for i in range(len(liste)):
        min = i
        j = min+1
        while j < len(liste) and liste[min] > liste[j]:
            min = j
            j = j+1
        _temp = liste[i]
        liste[i] = liste[min]
        liste[min] = _temp
        i = i+1
    return liste			

Invariant et preuve de terminaison

Intérêt

Il n'est pas évident de savoir si un algorithme fonctionne correctement dans tous les cas. Il se peut très bien que l'algorithme fonctionne dans les cas de test mais qu'il existe au moins un cas, non testé, où l'algorithme ne fonctionne pas.

Certains algorithmes peuvent semblaient au premier regard corrects et même fonctionner sur des premiers tests (cf. l'algorithme tri_3 de l'exercice 12 supra).

Comme un ne peut pas tester tous les cas possibles pour prouver qu'il n'existe aucun cas où l'algorithme dysfonctionne :

Comment être sûr que lorsqu'un algorithme renvoie un résultat, que ce résultat est forcément celui attendu ?

Il existe un moyen de démontrer (au sens mathématique du terme) la correction d'un algorithme : il suffit d'utiliser un invariant de boucle

Un outil d'une puissance ... !

Considérons d'abord un algorithme plus simple que les deux algorithmes de tri vu précédemment. Voici son écriture en langage courant :

1 Saisir une valeur pour n				
2 p←1							
3 Pour  i  allant de 1 à n faire
4 	p←p*2
5 Fin_Pour			
6 Afficher la valeur de p			

Dans l'algorithme précédent, la boucle considérée est la boucle Pour commençant à la ligne 3.

Considérons la propriété suivante : après la $i^{\text{ème}}$ itération, $p=2^i$

Nous allons montrer que cette propriété est un invariant de la boucle Pour de algorithme précédent.

Première étape : INITIALISATION

Avant le début de la boucle Pour, $p$ vaut 1 d'après la ligne 2 de l'algorithme.

Avant la première itération, la propriété $p=2^i$ est vraie car $2^0=1$.

Nous avons donc montré que la propriété est vraie avant la première itération.

Deuxième étape : CONSERVATION

On choisit de se placer à une itération quelconque $i$. Et on suppose que la propriété est vraie donc $p=2^{i}$.

On procède alors à l'itération.

On alors $p$ qui devient $2^{i}\times 2=2^{i+1}$. Après l'itération $i+1$ on a bien $p=2^{i+1}$.

Vous pouvez visualiser cette étape avec le tableau suivant :

Dernière étape : TERMINAISON :

La propriété $p=2^i$ est un invariant de la boucle Pour de algorithme précédent.

Ainsi, à la fin de la boucle for lorsque $i=n$, $p$ contient la valeur $2^n$ ; l'algorithme renverra donc bien la valeur de $2^n$.

def mystere(k: int, p: int) -> int:
    m = 1
    i = 0
    while m < p:
        m = m*k
        i += 1
    return m			

Invariant du tri par insertion

On rappelle l'algorithme du tri par insertion écrit en langage Python vu dans la première partie :

def tri_insertion(lst: list) -> list:
    for i in range(1, len(lst)):
        elt = lst[i]
        j = i 
        while elt < lst[j-1] and j > 0:
            lst[j] = lst[j-1]
            j -= 1
        lst[j] = elt
    return lst

Nous avons vu qu'il faut insérer dans une liste déjà triée le premier terme non trié. Dès lors, la liste lst est découpée en 2 parties :

1. la première partie qui contient les éléments déjà triés : ceux d'index 0 à $i-1$ (le $i$ correspond à la variable $i$ dans l'algorithme ci-dessus). Cette partie peut être notée lst[:i],

2. la seconde partie qui contient les éléments à trier : ceux d'index $i$ à $n-1$. Cette partie peut être notée lst[i:].

À chaque itération, la première partie de la liste contenant les éléments déjà triés est augmentée d'un terme : celui lst[i] placé correctement.
Au vu de cette première partie, l'invariant de boucle de la boucle for de ce tri est "À l'issue de l'itération $i$, les termes d'index 0 à $i$ sont rangés par ordre croissant.".

Invariant du tri par sélection

On rappelle ci-dessous l'algorithme du tri par sélection écrit en langage Python vu dans la seconde partie :

def tri_selection(lst):
    for i in range(len(lst)-1):
        min = i 
        for j in range(i+1, len(lst)):
            if lst[min] > lst[j]:
                min = j 
        lst[i], lst[min] = liste[min], lst[i]
    return lst

Nous avons vu qu'il faut rajouter à une liste déjà triée le minimum des termes non triés. Dès lors, la liste lst est découpée en 2 parties :

1. la première partie qui contient les éléments déjà triés : ceux d'index 0 à $i-1$ (le $i$ correspond à la variable $i$ dans l'algorithme ci-dessus). Cette partie peut être notée lst[:i],

2. la seconde partie qui contient les éléments à trier : ceux d'index $i$ à $n-1$. Cette partie peut être notée lst[i:].

Exercices de renforcement

Les corrections des exercices de cette partie (hormis le 20 pour lequel un lien direct est proposé) sont disponibles sur le jupyter disponible ici.

Voici un tableau pouvant servir comme trace d'exécution :

lst = ['Belgique', 'Pologne', 'Suède', 'Allemagne', 'France', 'République Tchèque', 'Portugal'] 

def mystere(tab, valeur):
    """
    tab – liste d'entiers triée par ordre décroissant
    valeur – entier
    Sortie : …………………………………………………………………………………………………………………………………
    """
    return [x for x in tab if x >= valeur] + [valeur] + [x for x in tab if x < valeur]
            

Compléments pour approfondir

Un autre tri

Encore un autre tri : le tri rapide

1    initialiser ipivot à ideb    
2   Tant que ideb < ifin faire  #(tant qu'il reste des valeurs mal placées par rapport à la valeur pivot)
3       Tant que la valeur correspondant à ifin est plus grande strictement que la valeur du pivot faire
4           on décrémente ifin.
5       Fin Tant que   #(ainsi ifin correspond soit à l'indice du pivot soit du premier terme rencontré par la droite qui est inférieur ou égal à la valeur du pivot)
6       Tant que la case correspondant à ideb est inférieure ou égale au pivot et ideb est plus petit que ifin faire
7           on incrémente ideb.
8       Fin Tant que   #(ainsi ideb correspond soit à l'indice ifin soit du premier terme rencontré par la gauche qui est strictement supérieur à la valeur du pivot)
9       Si ideb < ifin alors    #(cas où ideb correspond à l'index d'une valeur strictement supérieure à celle du pivot)
10           échanger la valeur d'indice ideb et la valeur d'indice ifin.  #(Ainsi, la valeur trouvée strictement plus grand que le pivot est permutée soit avec une valeur inférieure ou égale à celle du pivot)
11      Fin si
12  Fin Tant que
13  Si ifin est différent de ipivot alors  #(ideb et ifin indique la valeur la plus à droite inférieure ou égale à celle du pivot : on permute le pivot (premier élément de la liste) avec cette valeur)
14      échanger la valeur d'indice ipivot et la valeur d'indice ifin.
15  Fin si

Comparaison de temps de calcul

On admet dans cette partie que l'algorithme de tri rapide peut s'écrire ainsi (les appels à elle-même de la procédure correspondent à la notion de récursivité) :

def tri_rapide(liste: list, ideb: int, ifin: int) -> None:
    """
    Le premier argument de tri_rapide est la liste à triée.
    Le tri_rapide s'appliquera sur l'ensemble des éléments dont l'index est compris entre ideb et ifn, inclus.
    """
    _id = ideb
    _if = ifin
    while ideb < ifin:
        while liste[ifin] > liste[_id]:
            ifin -= 1
        while liste[ideb] ≤ liste[_id] and ideb < ifin:
            ideb += 1
        if ideb < ifin:
            _temp = liste[ideb]
            liste[ideb] = liste[ifin]
            liste[ifin] = _temp
    if _id != ifin:
        _temp = liste[ifin]
        liste[ifin] = liste[_id]
        liste[_id] = _temp
    if ifin - _id > 1:
        tri_rapide(liste, _id, ifin-1)   # appel récursif sur la partie à gauche du pivot
    if _if - ifin > 1:
        tri_rapide(liste, ifin+1, _if)   # appel récursif sur la partie à droite du pivot
    return None

from timeit import default_timer as timer
from random import randint

# définition de chacun des tris :
# tri par insertion
def tri_insertion(liste: list) -> None:
    for i in range(1, len(liste)):			# le premier élément forme seul une liste classée
        elt = liste[i] 						# élément à classer
        j = i
        while elt < liste[j-1] and j > 0:	# permutation avec le précédent s'il est plus grand
            liste[j] = liste[j-1]
            j -= 1
        liste[j] = elt						# placement au bon endroit
    return None

# tri par sélection
def tri_selection(liste: list) -> None:
    for i in range(1, len(liste)):
        j = i
        elmt = liste[i]
        while j > 0 and liste[j-1] > elmt:
            liste[j] = liste[j-1]
            j -= 1
        liste[j] = elmt
    return None

# tri à bulles
def tri_bulle(liste: list) -> None:
    i = 0
    continuer = True
    while i < len(liste) and continuer:
        continuer = False
        for j in range(len(liste) - i - 1):
            if liste[j] > liste[j+1]:
                _temp = liste[j]
                liste[j] = liste[j+1]
                liste[j+1] = _temp
                continuer = True
    return None

# tri rapide
def tri_rapide(liste: list, ideb: int, ifin: int) -> None:
    """
    Le premier argument de tri_rapide est la liste à triée.
    Le tri_rapide s'appliquera sur l'ensemble des éléments dont l'index est compris entre ideb et ifn, inclus.
    """
    _id = ideb
    _if = ifin
    while ideb < ifin:
        while liste[ifin] > liste[_id]:
            ifin -= 1
        while liste[ideb] <= liste[_id] and ideb < ifin:
            ideb += 1
        if ideb < ifin:
            _temp= liste[ideb]
            liste[ideb] = liste[ifin]
            liste[ifin] = _temp
    if _id!=ifin:
        _temp= liste[ifin]
        liste[ifin] = liste[_id]
        liste[_id] = _temp
    if ifin - _id > 1:
        tri_rapide(liste, _id, ifin-1)   # appel récursif sur la partie à gauche du pivot
    if _if - ifin > 1:
        tri_rapide(liste, ifin+1, _if)   # appel récursif sur la partie à droite du pivot
    return None

# création des listes sur lesquelles vont porter les tris
tab = []
for i in range(20):
    tab.append([randint(0,100) for i in range(1000)])

# mesure des temps d'exécution
n= len(tab[1])
# cas du tri rapide
start = timer()
# tâches dont on veut mesurer le temps d'exécution.
for i in range(20):
    tri_rapide(tab[i].copy(), 0, n-1)
end = timer()
print("temps moyen pour le tri rapide :", (end - start)/20) # affichage du temps écoulé

# cas du tri par insertion
start = timer()
# tâches dont on veut mesurer le temps d'exécution.
for i in range(20):
    tri_insertion(tab[i].copy())
end = timer()
print("temps moyen pour le tri par insertion :", (end - start)/20) # affichage du temps écoulé

# cas du tri par sélection
start = timer()
# tâches dont on veut mesurer le temps d'exécution.
for i in range(20):
    tri_selection(tab[i].copy())
end = timer()
print("temps moyen pour le tri par sélection :", (end - start)/20) # affichage du temps écoulé

# cas du tri à bulles
start = timer()
# tâches dont on veut mesurer le temps d'exécution.
for i in range(20):
    tri_bulle(tab[i].copy())
end = timer()
print("temps moyen pour le tri à bulles :", (end - start)/20) # affichage du temps écoulé

QCM

Questions issues de la Banque Nationale de Sujets

Propriétaire des ressources ci-dessous : ministère de l'Éducation nationale et de la jeunesse, licence CC BY SA NC

Voici une sélection de questions issues de la banque nationale de sujets, répondez à ces questions (attention, cette sélection n'est pas exhaustive).

i = 0
somme = 0
while i < N :
    i = i +1
    somme = somme + i            

def tri (tab):
    for i in range (1, len(tab)):
        for j in range (len(tab) - i):
            if tab[j] > tab[j+1]:
                tab[j], tab[j+1] = tab[j+1], tab[j]
                

def trier(L): 
    for i in range(len(L)): 
        indice_min = i 
        for j in range(i+1, len(L)): 
            if L[j] < L[indice_min]: 
                indice_min = j 
                L[i], L[indice_min] = L[indice_min], L[i] 
                # assertion vraie à cet endroit
    return L                    

Autres QCM

Les deux QCM suivants sont issus de https://genumsi.inria.fr.

def tri_selection(t) :
    for i in range (len(t)-1) :
        min = i
        for j in range(i+1, len(t)):
            if t[j] < t[min]:
                min = j
        tmp = t[i]
        t[i] = t[min]
        t[min] = tmp    

def tri_selection(t) :
    for i in range (len(t)-1) :
        min = i
        for j in range(i+1, len(t)-1):
            if t[j] < t[min]:
                min = j
        tmp = t[i]
        t[i] = t[min]
        t[min] = tmp

def tri_selection(t) :
    for i in range (len(t)-1) :
        min = i
        for j in range(i+1, len(t)):
            if t[j] < min:
                min = j
        tmp = t[i]
        t[i] = t[min]
        t[min] = tmp    

def tri_selection(t) :
    for i in range (len(t)-1) :
        min = i
        for j in range(i+1, len(t)):
            if t[j] < t[min]:
                min = j
        tmp = t[i]
        t[min] = t[i]
        t[i] = tmp     

        nom: tri_sélection

        paramètre: tab, tableau de n entiers, n>=2
        
        Traitement:
        pour i allant de 1 à n-1:
            pour j allant de i+1 à n:
                si tab[j] < tab[i]:
                    echanger(tab[i], tab[j])
        renvoyer tab     

Générateur aléatoire de questions sur ce chapitre

Il faut actualiser la page pour changer de question. Propriétaire de la ressource : le site GeNumsi en licence CC BY_NC-SA

Sitographie

Voici une liste de sites traitant des tris :

• sur le tri par insertion

• sur le tri par sélection

Savoir faire et Savoir