Walking through the quicksort subroutine

As discussed previously, quicksort uses the following subroutine, implemented in JavaScript, to rearrange the elements in an array.

partition.test.js

const expect = require('chai').expect;
const partition = require('./partition');

describe('partition', () => {
    it('rearranges `arr` from [46,50,99,32,49] to [46,32,49,50,99] and returns 2', () => {
        const arr = [46,50,99,32,49];
        const p = 0;
        const r = arr.length - 1;
        const actual_q = partition(arr,p,r);
        const expected_arr = [46,32,49,50,99];
        const expected_q = 2;
        expect(expected_arr).to.deep.equal(arr); // in-place sorting
        expect(expected_q).to.equal(actual_q)
    });
});

partition.js

module.exports = (arr, p, r) => {
    let i = p - 1;
    for (let j = p; j < r; j++) {
        if (arr[j] <= arr[r]) {
            i += 1;
            exchange(arr, i, j);
        }
    }
    const q = i + 1;
    exchange(arr, q, r);
    return q;
}

// helper function
const exchange = (arr, i, j) => {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Now, we will walk through what the subroutine does for the unit test above. Note that

• p is used to set the initial values of i and j,
• inside the loop, the values located at i (incremented before the exchange) and j are only exchanged if arr[j] is less than or equal to arr[r], as is the case when j = 0 and j = 3 in this example, and,
• after the loop, the values located at q (set to i + 1) and r are exchanged.