De ce contează?
Imaginează-ți că aranjezi un teanc de cărți de joc. Poți face asta în trei feluri: inversezi mereu vecinii până nu mai ai ce schimba (bubble), cauți de fiecare dată cartea cea mai mică și o pui la rând (selection), sau iei cărțile una câte una și o strecori pe fiecare la locul ei în mâna deja sortată (insertion). Trei gesturi diferite, dar același efort total când teancul e mare: cam jumătate de tablă de comparații, una pentru fiecare pereche.
Intuiția
Cele trei sortări „pătratice” sortează prin comparații simple între elemente, fără
trucuri. Diferă mecanica — cum aleg ce să mute — dar nu și ordinul de mărime al
efortului: fiecare face în jur de n^2/2 comparații. Asta le face limpezi de
înțeles și sigure, dar lente la n mare. Le înveți ca să vezi de ce o sortare
ia atâtea comparații, înainte de a trece la sortările rapide.