Run results for: Quick Sort

Run details:

User agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:106.0) Gecko/20100101 Firefox/106.0

Browser: Firefox 106

Operating system: Ubuntu

Device Platform: Desktop

Date tested: 2 years ago

Test name	Executions per second
Quick Sort A	340991.0 Ops/sec
Quick Sort B	306184.4 Ops/sec
Stable Sort	656849.4 Ops/sec
Quick Sort C	2477854.8 Ops/sec
Quick Sort D	2224862.0 Ops/sec

Script Preparation code:

var test = [1,10,5,4,8,3,2,11,9,7,6,0];
function quickSortA(array){
if(array.length < 2){
  return array;
}
var last = array.length-1;
var pivot = array[last];
var left = [], right = [], mid = [];

for(var i=0; i<array.length; i++){
  if(array[i] < pivot){
    left.push(array[i]);
  }else if(array[i] > pivot){
    right.push(array[i]);
  }else{
    mid.push(array[i]);
  }
}
return partition(left,mid,right);

}

function partition(left,mid,right){
  left = quickSortA(left);
  right = quickSortA(right);
  return left.concat(mid).concat(right);
}

function quickSortB(array){
  if(array.length < 2){
    return array;
  }
  var pivot = array[Math.floor(Math.random()*array.length)]
  var left = [], right = [], mid = [];
  
  for(var i=0; i<array.length; i++){
    if(array[i] < pivot){
      left.push(array[i]);
    }else if(array[i] > pivot){
      right.push(array[i]);
    }else{
      mid.push(array[i]);
    }
  }
  return quickSortB(left).concat(mid).concat(quickSortB(right));
}

function stableSort(v, f)
{
    if (f === undefined) {
        f = function(a, b) {
            a = ""+a; b = ""+b;
            return a < b ? -1 : (a > b ? 1 : 0);
        }
    }
    var dv = [];
    for (var i=0; i<v.length; i++) {
        dv[i] = [v[i], i];
    }
    dv.sort(function(a, b){
              return f(a[0], b[0]) || (a[1] - b[1]);
            });
    for (var i=0; i<v.length; i++) {
        v[i] = dv[i][0];
    }
}


function quickSortC(arr, left, right)
{
	var i = left;
	var j = right;
	var tmp;
	pivotidx = (left + right) / 2; 
	var pivot = parseInt(arr[pivotidx.toFixed()]);  
	/* partition */
	while (i <= j)
	{
		while (parseInt(arr[i]) < pivot)
		i++;
		while (parseInt(arr[j]) > pivot)
			j--;
		if (i <= j)
		{
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	}

	/* recursion */
	if (left < j)
		quickSort(arr, left, j);
	if (i < right)
		quickSort(arr, i, right);
	return arr;
}


function quickSortD(t){
    _quickSort(t,0,t.length-1,0,t.length-1);
}

function _quickSort(t, s, e, sp, ep){   
    if( s>=e )  return;
    while( sp<ep && t[sp]<t[e] ) sp++;  
    if( sp==e )
        _quickSort(t,s,e-1,s,e-1);  
    else{
        while(t[ep]>=t[e] && sp<ep ) ep--;      
        if( sp==ep ){
            var temp = t[sp];
            t[sp] = t[e];
            t[e] = temp;
            if( s!=sp ){
                _quickSort(t,s,sp-1,s,sp-1);
            }
            _quickSort(t,sp+1,e,sp+1,e);            
        }else{
            var temp = t[sp];
            t[sp] = t[ep];
            t[ep] = temp;
            _quickSort(t,s,e,sp+1,ep);
        }
    }
}

Tests:

Quick Sort A
quickSortA(test);
Quick Sort B
quickSortB(test);
Stable Sort
stableSort(test);
Quick Sort C
quickSortC(test);
Quick Sort D
quickSortD(test);

Run results for: Quick Sort

Test of Quick Sort Implementations

Quick Sort A

Quick Sort B

Stable Sort

Quick Sort C

Quick Sort D