Mes Planches
TRI RAPIDE

1 / 5 · mockup · meeting-oak

TRI RAPIDE

partitionnement autour d'un pivot · la trace d'une exécution réelle

Faite comme un mémo plutôt qu'un tableau : en haut ce pour quoi on l'accroche et qui se lit à travers la pièce, en dessous la référence complète en plus petit.

Trois formats dans une seule archive — de la feuille sur le frigo à l'affiche murale.

Premium2,50 $US

En cliquant sur Acheter, vous acceptez les Conditions et Remboursements.

Le paiement et l'e-mail sont gérés par Paddle. Le lien de téléchargement arrive par e-mail — pas de compte, pas de mot de passe.

Formats
A4 · A3 · A2
Ce que vous recevez
Des PDF prêts à imprimer, un par format, toutes les lettres converties en contours — rien à installer, rien ne bouge.
Sujet
code · débutants · mémo · bureau

La trace et tous les chiffres de cette planche viennent d'une exécution réelle de l'algorithme sur le tableau montré ; les comparaisons sont comptées pendant l'exécution, pas tirées d'une formule.

LE PIRE CAS DU TRI RAPIDE EST UN TABLEAU DÉJÀ TRIÉ

Le partitionnement sur le dernier élément coûte 329 comparaisons sur 64 nombres mélangés. Sur les mêmes 64, déjà triés, il en coûte 2016 : chaque partition retire exactement un élément, et au lieu de moitiés, on obtient un escalier.

Le pire cas n'est donc pas une coïncidence rare, mais les données les plus ordinaires qui soient. C'est pourquoi les bibliothèques choisissent le pivot au hasard ou prennent la médiane de trois valeurs.

Le nom « tri rapide » décrit le cas moyen, pas une promesse. Un algorithme qui se comporte au pire sur des données triées mérite l'attention précisément pour ce dont il faut le protéger.

Sur la planche

  • La trace et tous les chiffres de cette planche viennent d'une exécution réelle de l'algorithme sur le tableau montré ; les comparaisons sont comptées pendant l'exécution, pas tirées d'une formule.
  • La couleur porte du sens, mais le sens ne repose jamais sur elle seule — la planche se lit aussi en noir et blanc.
  • Rien sur la façon dont elle a été faite : la planche ne porte que ce dont le lecteur a besoin.

Impression

  • Trois formats dans l'archive : A4 — 210×297 mm, A3 — 297×420 mm, A2 — 420×594 mm.
  • Tout le texte est converti en contours. Rien à installer, rien ne bouge sur une autre machine.
  • Fond blanc et remplissages économes — elle s'imprime sur une imprimante domestique sans vider la cartouche.
  • Marges d'au moins 10 mm : une imprimante domestique n'imprime pas à bord perdu.
  • Aucun trait plus fin que 0,3 mm, pour que rien ne disparaisse à l'impression.

Pourquoi on peut faire confiance aux chiffres. Chaque nombre dénombrable ici est calculé à partir de données, pas saisi à la main, et la planche doit passer 4 contrôles indépendants avant d'être autorisée à être construite — combien d'éléments, dans quel ordre, et l'affirmation de l'encadré mis en avant. Si l'un échoue, il n'y a pas de fichier.

Dans le même esprit

BITS, BYTES, KILOBYTES

BITS, BYTES, KILOBYTES

deux échelles · 1000 et 1024 · pourquoi un disque semble « rétrécir »

1,50 $US
CODES DE STATUT HTTP

CODES DE STATUT HTTP

cinq classes · vingt codes que vous croisez chaque jour

1,50 $US
PYTHON vs GO

PYTHON vs GO

sept questions, les mêmes aux deux, et le document où chaque réponse est écrite

1,50 $US
PYTHON vs JAVASCRIPT

PYTHON vs JAVASCRIPT

sept questions, les mêmes aux deux, et le document où chaque réponse est écrite

1,50 $US