Principe de base :

1. Sélectionner le premier élément de la liste comme pivot, puis partitionner la liste en deeux sous-listes : une avec des éléments plus petits que le pivot, l'autre avec des éléments plus grands.
2. Appliquer l'étape 1 à la première sous-liste.
3. Appliquer l'étape 1 à la seconde sous-liste.

Code – Liste 1.1

public class TriRapideA {

    public static int[] triRapide(int[] tableauNonTrié, int gauche, int droite) {
        // Partitionnement récursif
        if (gauche < droite) {
            int positionPivot = partitionner(tableauNonTrié, gauche, droite);
            triRapide(tableauNonTrié, gauche, positionPivot - 1);
            triRapide(tableauNonTrié, positionPivot + 1, droite);
        }
        return tableauNonTrié;
    }

    private static int partitionner(int[] tableau, int bas, int haut) {
        // Prendre le premier élément comme pivot et partitionner
        int pivot = tableau[bas];
        int pointeurGauche = bas;
        int pointeurDroit = haut + 1;    // Pour que --pointeurDroit pointe sur le dernier élément
        while (true) {
            while (tableau[++pointeurGauche] <= pivot) {
                if (pointeurGauche == haut) break;
            }
            while (tableau[--pointeurDroit] >= pivot) {
                if (pointeurDroit == bas) break;
            }
            if (pointeurGauche >= pointeurDroit) break;
            échanger(tableau, pointeurGauche, pointeurDroit);
        }
        échanger(tableau, bas, pointeurDroit);
        return pointeurDroit;
    }

    private static void échanger(int[] tableau, int i, int j) {
        int temp = tableau[i];
        tableau[i] = tableau[j];
        tableau[j] = temp;
    }
}

Code – Liste 1.2 (même méthode partitionner que ci-dessous, le reste identique)

    private static int partitionner(int[] tableau, int bas, int haut) {
        int pivot = tableau[bas];
        int pointeurGauche = bas;
        int pointeurDroit = haut;    // Défaut intentionnel (Seeded Fault)
        while (true) {
            while (tableau[++pointeurGauche] < pivot) {
                if (pointeurGauche == haut) break;
            }
            while (tableau[--pointeurDroit] > pivot) {
                if (pointeurDroit == bas) break;
            }
            if (pointeurGauche >= pointeurDroit) break;
            échanger(tableau, pointeurGauche, pointeurDroit);
        }
        échanger(tableau, bas, pointeurDroit);
        return pointeurDroit;
    }

Résultat de l'exécution de 30 tests

Tests réussis : 9, échecs : 21

public class TestTriRapideA {

    @Test
    public void test1() {
        int[] A = {};
        TriRapideA.triRapide(A, 0, 0);
        int[] result = {};
        assertArrayEquals(result, A);
    }

    @Test
    public void test2() {
        int[] A = { 1 };
        TriRapideA.triRapide(A, 0, 0);
        int[] result = { 1 };
        assertArrayEquals(result, A);
    }

    @Test
    public void test3() {
        int A[] = { 1, 2, 3, 4 };
        TriRapideA.triRapide(A, 0, A.length - 1);
        int[] result = { 1, 2, 3, 4 };
        assertArrayEquals(result, A);
    }

    @Test
    public void test4() {
        int A[] = { 2, 5, 1, 3, 6, 1 };
        TriRapideA.triRapide(A, 0, A.length - 1);
        int[] result = { 1, 1, 2, 3, 5, 6 };
        assertArrayEquals(result, A);
    }

    // … (les tests 5 à 30 sont omis pour la concision, mais identiques à l'original en structure)
}

Localisation de défaut à partir des résultats de test

En utilisant les algorithmes Ochia, Jaccard, Tarantula et Naish2 sur la Liste 1.2, les codes suspects sont indiqués ci-dessous :

On cnostate que la locailsation pointe vers du code suspect qui n'est pas la véritable instruction erronée (lignes surlignées en bleu clair).