Mini-défi : trier sans sort()
Trier un tableau de nombres sans utiliser sort().
Objectifs
Écrire un algorithme de tri sans Array.prototype.sort(), en combinant tout ce que vous savez : parcours, minimum, copie de tableau, accumulation, mutation contrôlée.
🔗 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 sans traitement particulier.
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 — dites-la à voix haute, c'est déjà l'algorithme :
- 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 une composition d'algorithmes déjà maîtrisés : minimum (leçon 5-02) + retrait d'un élément + boucle globale. Aucune brique nouvelle à inventer.
Indices
Indice 1. Travaillez sur une copie du tableau ([...nombres]) que vous êtes autorisé à muter ; l'original reste intact. C'est le réflexe « copie superficielle » du chapitre 4 appliqué en conditions réelles.
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;
}
C'est le minimum connu, adapté pour retourner l'index plutôt que la valeur — car pour retirer l'élément, il faudra savoir où il est.
Indice 3. Pour retirer un élément par sa position : copie.splice(position, 1) retire et renvoie un tableau contenant l'élément concerné. Méthode native mutatrice — acceptable ici précisément parce qu'on agit sur notre propre copie.
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 demandées
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] ✓ intact
Trace détaillée avec [3, 1, 2]
Suivez les deux tableaux tour par tour — c'est le cœur pédagogique du défi :
départ : reste = [3, 1, 2] resultat = []
tour 1 : min de reste = 1, en position 1
splice(1, 1) → reste = [3, 2]
push(1) → resultat = [1]
tour 2 : min de reste = 2, en position 1
splice(1, 1) → reste = [3]
push(2) → resultat = [1, 2]
tour 3 : min de reste = 3, en position 0
splice(0, 1) → reste = []
push(3) → resultat = [1, 2, 3]
fin : reste est vide → while s'arrête → return [1, 2, 3]
Les cas limites tombent seuls : tableau vide → le while ne démarre jamais → résultat []. Doublons → deux valeurs 8 sont simplement deux minima successifs indépendants. Un seul élément → un seul tour. Aucun if spécial n'a été nécessaire : encore une conception qui « absorbe » ses cas limites.
Pourquoi c'est correct : raisonner par invariant
Comment être sûr que l'algorithme marche sur TOUTES les entrées, pas seulement celles testées ? Par un argument d'invariant — une propriété vraie avant et après chaque tour :
Après chaque tour,
resultatcontient les plus petits éléments de l'entrée, triés, etrestecontient tous les autres, dans leur ordre initial.
- Vrai au départ ? Oui :
resultatvide,reste= tout. - Si vrai avant un tour, vrai après ? Oui : on extrait le minimum de et on le place en fin de — donc plus grand ou égal à tout ce qui y était déjà, et plus petit ou égal à tout ce qui reste.