Exercice : Tri par sélection

Exercice : Tri par sélection#

À faire

2025-2026

Avec des vector plutôt que des array C, il serait plus facile d’écrire des tests et le passage d’argument serait plus simple en faisant travailler les références. D’un autre côté, ici on fait travailler les array C. Qu’est-ce qui serait plus pertinent?
Pour plus de cohérence, nommer le fichier comme la fonction; typiquement triselection.md
Prendre comme invariant « les k plus petits éléments … ». Ça évite une boucle descendante et c’est cohérent avec l’exemple de la wikipedia.

Dans ce premier exercice vous devez implémenter le tri par sélection vu en cours. Pour rappel, c’est un tri itératif dans lequel, après \(k\) étapes, la condition suivante soit respectée «la fin du tableau contient les \(k\) plus grandes valeurs du tableau d’origine, triées, tandis que le début du tableau contient les valeurs restantes, non encore triées».

À l’étape \(k+1\), on cherche la plus grande valeur dans la première partie du tableau, puis on échange cette valeur avec celle placée juste avant la deuxième partie. Cette valeur est maintenant à sa place définitive et l’on a progressé vers un tableau complètement trié.

Pour en savoir plus

Cette condition décrivant l’état de l’algorithme après \(k\) étapes est appelée un invariant (car elle reste invariablement vraie à chaque étape de l’algorithme). On peut s’appuyer dessus:

Pour guider l’écriture de l’algorithme
Pour prouver par récurrence que l’algorithme est correct.

Exercice

Sur une feuille de papier, appliquez l’algorithme de tri sélection au tableau suivant [3, 13, 1, 2, 5, 10, 2, 8]. Pour cela, procédez par étapes :
1. Relisez la condition ci-dessus.
2. Que dit-elle sur l’état souhaité du tableau après la première étape (\(k=1\))?
3. Échangez deux valeurs du tableau pour y parvenir.
4. Procédez de mêmes pour les étapes 2, puis 3, etc : que dit la condition sur l’état souhaité du tableau? Échangez deux valeurs pour parvenir à cet état.
Définissez une fonction echanger qui étant donnés un tableau T et deux indices a et b échange les deux valeurs aux indices donnés :
```
void echanger(int T[], int a, int b) {
```

Définissez une fonction triselection avec le prototype suivant :

void triselection(int T[], int n);

BEGIN SOLUTION

void echanger(int T[], int a, int b) {
    int temp = T[a];
    T[a] = T[b];
    T[b] = temp;
}

void triselection(int T[], int N) {
    for (int i = N; i > 1; i--) {
	int max = T[0], idx = 0;
	for (int j = 1; j < i; j++) {
	    if (T[j] > max) {
		max = T[j];
		idx = j;
	    }
	}
	echanger(T, idx, i - 1);
    }
}

int main() {
    int T0[] = {};
    triselection(T0, 0);

    int T1[] = {42};
    triselection(T1, 1);
    CHECK( T1[0] == 42 );

    int N = 40;
    int T[N];
    for (int i = 0; i < N; i++)
	T[i] = rand() % 100;
    triselection(T, N);
    for (int i = 0; i < N; i++)
	cout << T[i] << " ";
    cout << endl;
    return 0;
}

END SOLUTION

Testez votre fonction afin de vérifier que le tri est bien réalisé. Pour cela, il vous est conseillé de trier le tableau que vous avez traité à la main, puis

de traiter un tableau suffisamment grand rempli de valeurs aléatoires et enfin de bien réfléchir aux cas limites.

Indication: nombres et tableaux aléatoires

Vous avez déjà construit des tableaux aléatoires. Vous souvenez-vous de quand?

Au premier semestre, lorsque vous avez lancé des dés pour le jeu de Yams! Ouvrez la page web de Programmation Impérative, et utilisez l’outil de recherche pour retrouver le sujet de TP.