Benchmark: Quick Sort - MeasureThat.net

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);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Quick Sort A
Quick Sort B
Stable Sort
Quick Sort C
Quick Sort D

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one month ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/134.0.0.0 Safari/537.36

Browser/OS: Chrome 134 on Windows

View result in a separate tab

Test name	Executions per second
Quick Sort A	467160.3 Ops/sec
Quick Sort B	388432.3 Ops/sec
Stable Sort	1715933.2 Ops/sec
Quick Sort C	12515358.0 Ops/sec
Quick Sort D	6490583.5 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

LLMs can make mistakes. Check important info.

Let's dive into the world of Quick Sort benchmarks.

**What is tested?**

The provided JSON represents two types of Quick Sort implementations: Quick Sort A and Quick Sort B, as well as two additional algorithms: Stable Sort and Quick Sort C/Quick Sort D. Each implementation is compared to measure their performance on a given test case (`test`).

Here's a brief overview of each algorithm:

1. **Quick Sort A**: A traditional recursive implementation of Quick Sort.
2. **Quick Sort B**: Another recursive implementation, but with some optimizations (not specified in the benchmark).
3. **Stable Sort**: An iterative sorting algorithm that maintains the stability of the input data.
4. **Quick Sort C** and **Quick Sort D**: Two optimized iterative implementations of Quick Sort.

**Performance characteristics**

The latest benchmark results show that:

* Quick Sort A performs relatively poorly, with an average execution speed of approximately 460,000 instructions per second (ips).
* Quick Sort B is faster than Quick Sort A, but still lags behind the other two algorithms.
* Stable Sort outperforms all three Quick Sort implementations, with an average execution speed of around 823,000 ips.
* Quick Sort C/Quick Sort D are nearly tied, with an average execution speed of approximately 830,000 and 820,000 ips, respectively.

**Key observations**

* The performance difference between Quick Sort A and B is relatively small, suggesting that the optimizations in Quick Sort B may not have a significant impact on performance.
* Stable Sort's superior performance indicates its stability features are beneficial for certain use cases.
* Quick Sort C/Quick Sort D's near-tie suggests that their iterative implementation and optimizations have reduced overhead compared to traditional recursive implementations.

**Considerations**

When choosing an algorithm, consider the specific requirements of your application:

* If stability is crucial, Stable Sort might be a better choice.
* For optimal performance, consider using Quick Sort C or Quick Sort D, as they appear to offer the best balance between speed and efficiency.

Related benchmarks:

Quick Sort (version: 0)

Test of Quick Sort Implementations

Comparing performance of: Quick Sort A vs Quick Sort B vs Stable Sort vs Quick Sort C vs Quick Sort D

Created: 6 years ago by: Guest

Jump to the latest result

Quick Sort A

Quick Sort B

Stable Sort

Quick Sort C

Quick Sort D

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):