You can find on this page, javascript sources to explore the perturbability of quicksort. One the left, the original source code and on the right the instrumented one. The instrumentation consist by wrapping every perturbables literals or expressions by a method call. This mehod, named p takes two arguments: an unique index that identify the perturbation point and the original value. The method will perturb the value with a given probability. For instance, with a probrability 0.1%, 1 over 10 integer value will be perturbed by adding one to it. If the probability is 0, the two programs are semantically equivalent.

Sources

Original

function quicksort(array, beg, end) {
    var left = beg;
    var right = end;
    var pivot = array[beg + ((end - beg) / 2)];





    while (left <= right) {

        while (array[left] < pivot) {
            left++;
        }

        while (array[right] > pivot) {
            right--;
        }

        if (left <= right) {
            swap(array, left, right);
            left++;
            right--;
        }
    }
    if (beg < right) {
        sort(array, beg, right);
    }
    if (end > left) {
        sort(array, left, end);
    }
}

function swap( array, i, j) {
    var x = array[i];
    array[i] = array[j];
    array[j] = x;
}

Instrumented

function quicksort_instr(array, beg, end) {
    var left = p(0, beg);
    var right = p(1, end);
    var pivot = p(9,
        array[p(8,
         Math.floor(p(2, beg) +
              p(7, (p(5, (p(3, end) - p(4, beg))) / p(6, 2))))
    )]);

    while (p(12, p(10, left) <= p(11, right))) {

        while (p (16, p(14, array[p(13, left)]) < p(15, pivot))) {
            p(17, left++);
        }

        while ( p(21, p(19, array[p(18, right)]) > p(20, pivot))) {
            p(22, right--);
        }

        if ( p(25, p(23, left) <= p(24, right))) {
            swap(array, p(26, left), p(27, right));
            p(28, left++);
            p(29, right--);
        }
    }
    if (p (32, p(30, beg) < p(31, right) )) {
        quicksort_instr(array, p(33, beg), p(34, right));
    }
    if (p(37, p(35, end) > p(36, left))) {
        quicksort_instr(array, p(38, left), p(39, end));
    }
}

function swap(array, i, j) {
    var x = p(41, array[p(40, i)]);
    array[p(42,i)] = p(44, array[p(43, j)]);
    array[p(45,j)] = p(46, x);
}

About the perturbation points

In this implementation, we can find 46 perturbation points: 40 integers and 6 booleans. In the demo, we also allow users to activate different class of points described here:

  • Antifragile points have good correctness ratio: > 75%.
  • Robust points have a correctness ratio ranges from 75% to 50%.
  • Fragile point have a correctness ration lower than 50%.
This classification of point is based on the results of the related paper: Correctness Attraction: A Study of Stability of Software Behavior Under Runtime Perturbation. Index of point are reported in the following table according to their class:

Type/Class Antifragile Robust Fragile Number
Integer [2, 3, 4, 5, 6, 7, 8, 10, 11, 14, 17, 20, 22, 23, 28, 29, 31, 34, 35] [9, 15, 19] [0, 1, 13, 18, 24, 26, 27, 30, 33, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46] 40
Boolean [12] [16, 21, 25, 32, 37] 6
Number 20 3 23 46