Mini-défi : trier sans sort()
Trier un tableau de nombres sans utiliser sort().
Objectifs
Écrire un algorithme de tri sans utiliser Array.prototype.sort(), en combinant tout ce que vous savez : parcours, minimum, copie de tableau, accumulation.
🔗 Pour vous rafraîchir la mémoire : rechercher et dédupliquer · parcourir, sommer, compter
Énoncé
Écrivez trierCroissant(nombres) qui renvoie un nouveau tableau contenant les mêmes valeurs, ordonnées du plus petit au plus grand.
Contraintes :
- interdiction d'utiliser
.sort(); - le tableau d'origine ne doit jamais être modifié ;
- le tableau vide et les doublons doivent fonctionner.
const entree = [8, 3, 8, 1];
console.log(trierCroissant(entree)); // [1, 3, 8, 8]
console.log(entree); // [8, 3, 8, 1] : intact
Stratégie suggérée : le tri par sélection
L'idée en langage courant :
- chercher le plus petit élément restant ;
- le retirer de la liste « à traiter » et le placer dans la liste résultat ;
- recommencer jusqu'à épuisement.
C'est exactement la composition des algorithmes déjà écrits : minimum + copie sans un élément + boucle globale.
Indices
Indice 1. Travaillez sur une copie du tableau ([...nombres]) que vous êtes autorisé à muter ; l'original reste intact.
Indice 2. Pour trouver le plus petit restant avec sa position :
function positionDuMinimum(valeurs) {
let positionMin = 0;
for (let i = 1; i < valeurs.length; i++) {
if (valeurs[i] < valeurs[positionMin]) {
positionMin = i;
}
}
return positionMin;
}
Indice 3. Pour retirer un élément par sa position : copie.splice(position, 1) retire et renvoie l'élément concerné (méthode native à découvrir ici).
Indice 4. La boucle principale tourne autant de fois qu'il y a d'éléments : while (copie.length > 0).
Correction disponibleCherchez d’abord par vous-même.Voir la correction
Correction
Solution complète
function positionDuMinimum(valeurs) {
let positionMin = 0;
for (let i = 1; i < valeurs.length; i++) {
if (valeurs[i] < valeurs[positionMin]) {
positionMin = i;
}
}
return positionMin;
}
function trierCroissant(nombres) {
const reste = [...nombres]; // copie : on peut la vider sans risque
const resultat = [];
while (reste.length > 0) {
const pos = positionDuMinimum(reste);
const plusPetit = reste.splice(pos, 1)[0]; // retire et renvoie l'élément
resultat.push(plusPetit);
}
return resultat;
}
// Vérifications
console.log(trierCroissant([8, 3, 8, 1])); // [1, 3, 8, 8]
console.log(trierCroissant([])); // []
console.log(trierCroissant([5])); // [5]
console.log(trierCroissant([2, 2, 2])); // [2, 2, 2]
const original = [9, -1, 4];
console.log(trierCroissant(original)); // [-1, 4, 9]
console.log(original); // [9, -1, 4]
Explication étape par étape
Trace avec [3, 1, 2] :
reste = [3, 1, 2], resultat = []
tour 1 : min = 1 en position 1 → splice → reste [3, 2], resultat [1]
tour 2 : min = 2 en position 1 → splice → reste [3], resultat [1, 2]
tour 3 : min = 3 en position 0 → splice → reste [], resultat [1, 2, 3]
fin : la boucle while s'arrête, on retourne le résultat
Le tableau vide fonctionne naturellement : while ne démarre pas, résultat vide retourné. Les doublons aussi : deux valeurs 8 sont deux minima successifs indépendants.
Pourquoi c'est correct
Invariant : après chaque tour, resultat contient les plus petits éléments de l'entrée, triés, et reste contient tous les autres. Quand reste est vide, resultat est nécessairement le tri complet de l'entrée. Raisonner par invariant est la façon fiable de prouver un algorithme — vous venez de le faire.
Ce qu'il faut remarquer
Chaque tour fait un parcours complet du reste : pour n éléments, environ n + (n−1) + … + 1 comparaisons, soit de l'ordre de n²/2. Le sort() natif fait bien mieux sur les grandes listes — mais maintenant vous savez ce qu'il remplace. La prochaine leçon donne un vocabulaire précis à cette différence.