Test

Benchmark created on

Setup

const ar = [];
for (let i = 0; i < 1000000; i++) {
	ar.push(Math.floor(Math.random() * Number.MAX_SAFE_INTEGER));
}

Test runner

Ready to run.

Testing in
TestOps/sec
quick sort со случайным опорным
const qsort = (ar) => {
    const l = ar.length;
    if (l < 2) return ar;

    const i = Math.floor(Math.random() * (l - 1));
    const pivot  = [ar[i]];
    const left = [];
    const right = [];

    for (let k = 0; k < l; k++) {
        if (ar[k] < pivot[0]) {
            left.push(ar[k]);
        } else if (ar[k] > pivot[0]) {
            right.push(ar[k]);
        } else {
            pivot.push(ar[k]);
        }
    }

    return qsort(left).concat(pivot.slice(1), qsort(right));
}

qsort([...ar]);
ready
стандартный sort
[...ar].sort((a, b) => a - b);
ready
quick sort с фиксированным медианным опорным элементом
const qsort = (ar) => {
    const l = ar.length;
    if (l < 2) return ar;

    const i = Math.floor(ar.length / 2);
    const pivot  = [ar[i]];
    const left = [];
    const right = [];

    for (let k = 0; k < l; k++) {
        if (ar[k] < pivot[0]) {
            left.push(ar[k]);
        } else if (ar[k] > pivot[0]) {
            right.push(ar[k]);
        } else {
            pivot.push(ar[k]);
        }
    }

    return qsort(left).concat(pivot.slice(1), qsort(right));
}

qsort([...ar]);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.