Négatifs en tête

Invariant $I(i,k)$ : « $T[0:i]$ ne contient que des valeurs négatives, $T[i:k]$ que des valeurs positives ou nulles, et $T[k:n]$ n'a pas encore été examiné ».

• Initialisation : $I(0,0)$, les trois zones $[0:0]$, $[0:0]$, $[0:n]$.
• Progression : $I(i,k)\wedge k\ne n\wedge T[k]\ge 0\Rightarrow I(i,k+1)$ ; $I(i,k)\wedge k\ne n\wedge T[k]<0\Rightarrow I(i+1,k+1)$ après échange de $T[i]$ et $T[k]$ (la valeur positive $T[i]$ passe en fin de zone du milieu).
• Arrêt : $k=n$ ; les négatifs occupent $T[0:i]$.

static void negatifsEnTete(int[] T) { int n = T.length;
    int i = 0, k = 0;                 // I(0,0)
    while (k != n) {                  // I(i,k) et k ≠ n
        if (T[k] < 0) {               // échanger T[i] et T[k]
            int t = T[i]; T[i] = T[k]; T[k] = t;
            i = i + 1;
        }
        k = k + 1;                    // I(i,k)
    }                                 // I(i,n) : T[0:i] < 0 et T[i:n] ≥ 0
}

$n$ tours : $\Theta (n)$. Il y a un échange par valeur négative, donc $n$ échanges dans le pire cas (tableau entièrement négatif, où chaque échange échange une case avec elle-même). Sur le tableau

$$[3,-1,4,-1,-5,9,-2,6],$$

la fonction fait quatre échanges et donne

$$[-1,-1,-5,-2,4,9,3,6].$$

nom : T
valeurs : -1 -1 -5 -2 4 9 3 6
vert : 0..3
pointeurs : i=4 k=n
zone : 0..3 < 0
zone : 4..7 ≥ 0
legende : à l'arrêt, k = n : les négatifs occupent T[0:i]

L'ordre des positifs n'est pas conservé.