quick sort speed tests (v2)

Revision 2 of this 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 с разделением на лево-право и опорный элемент случайный
function qsort(arr) {
    if (arr.length < 2) return arr; 
    const k = Math.floor(Math.random() * (arr.length - 1));
    let pivot = arr[k]; 
    
    const left = [];
    const right = [];
    
  
    for (let i = 1; i < arr.length; i++) {
        if (pivot > arr[i]) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
    } 
    
    return qsort(left).concat(pivot, qsort(right));  
}

qsort([...ar]);
ready

Revisions

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