# Javascript Flashsort Comparisons

## JavaScript performance comparison

Revision 5 of this test case created by stacey reiman

## Preparation code

``````

<script>
Benchmark.prototype.setup = function() {
var arr = [];
var n = 50000; //array size we are sorting

for (var i = 0; i < n; i++) {
arr.push(parseInt(Math.random() * 10000));
}

/********************************************* SHUFFLE *****************************************************************/
//Fisher-Yates...aka..Knuth Shuffle
function shuffle(arr) {

var currentIndex = arr.length;
var temporaryValue;
var randomIndex;

// While there remain elements to shuffle...
while (0 !== currentIndex) {

// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;

// And swap it with the current element.
temporaryValue = arr[currentIndex];
arr[currentIndex] = arr[randomIndex];
arr[randomIndex] = temporaryValue;
}

return arr;
}
/*********************************** RECURSIVE QUICK SORT *************************************************************/
var StandardRecursiveQuicksort = (function() {

var standardRecursiveQS = {};

standardRecursiveQS.sort = function(arr) {
if (arr.length <= 1) {
return arr;
}
return recursiveQuickSort(arr, 0, arr.length - 1);
}

function recursiveQuickSort(arr, left, right) { //partition arrays so that everything to the left of pivot is less then pivot, and everything to the right is greater then pivot
var i = left;
var j = right;
var tmp;
var 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)
recursiveQuickSort(arr, left, j);
if (i < right)
recursiveQuickSort(arr, i, right);
return arr;
}
return standardRecursiveQS;
}());

/**********************************************************************************************************************/
/*************************************** Three Way Partition Quicksort ************************************************/
var ThreeWayPartitionQuicksort = (function() {

var ThreeWayPartionQuicksortModule = {};

//Private Variables
var CUTOFF = 8;  // cutoff to insertion sort, must be >= 1

ThreeWayPartionQuicksortModule.sort = function( a, lo, hi) { //Public function

if(typeof lo == "undefined" && typeof hi === "undefined"){
this.sort(a, 0, a.length - 1);
} else{
var N = hi - lo + 1;

// cutoff to insertion sort
if (N <= CUTOFF) {
insertionSort(a, lo, hi);
return;
}

// use median-of-3 as partitioning element
else if (N <= 40) {
var m = median3(a, lo, lo + N/2, hi);
exch(a, m, lo);
}

// use Tukey ninther as partitioning element
else  {
var eps = N/8; //TODO: verify these come out as integers
var mid = lo + N/2;
var m1 = median3(a, lo, lo + eps, lo + eps + eps);
var m2 = median3(a, mid - eps, mid, mid + eps);
var m3 = median3(a, hi - eps - eps, hi - eps, hi);
var ninther = median3(a, m1, m2, m3);
exch(a, ninther, lo);
}

// Bentley-McIlroy 3-way partitioning
var i = lo, j = hi+1;
var p = lo, q = hi+1;
var v = a[lo];
while (true) {
while (less(a[++i], v))
if (i == hi) break;
while (less(v, a[--j]))
if (j == lo) break;

// pointers cross
if (i == j && eq(a[i], v))
exch(a, ++p, i);
if (i >= j) break;

exch(a, i, j);
if (eq(a[i], v)) exch(a, ++p, i);
if (eq(a[j], v)) exch(a, --q, j);
}

i = j + 1;
for (var k = lo; k <= p; k++) exch(a, k, j--);
for (var k = hi; k >= q; k--) exch(a, k, i++);

this.sort(a, lo, j);
this.sort(a, i, hi);
}

}

// sort from a[lo] to a[hi] using insertion sort
function insertionSort( a, lo, hi) {
for (var i = lo; i <= hi; i++)
for (var j = i; j > lo && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}

// return the index of the median element among a[i], a[j], and a[k]
function median3( a, i, j, k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}

/***********************************************************************
*  Helper sorting functions
***********************************************************************/

// is v < w ?
function less(v, w) {
return (v < w); //java version uses compareto
}

// does v == w ?
function eq(v, w) {
return (v == w); //java version uses compareto
}

// exchange a[i] and a[j]
function exch(a, i, j) {
var  swap = a[i];
a[i] = a[j];
a[j] = swap;
}

return ThreeWayPartionQuicksortModule;
}());

/**********************************************************************************************************************/
/*************************************** Dual Pivot QuickSort *********************************************************/

var DualPivotQuicksort = (function() {

var dualPivotQS = {};

dualPivotQS.sort = function(arr, fromIndex, toIndex) {
if(fromIndex === undefined && toIndex === undefined){
this.sort(arr, 0, arr.length);
} else{
rangeCheck(arr.length, fromIndex, toIndex);
dualPivotQuicksort(arr, fromIndex, toIndex - 1, 3);
}
return arr;
}

function rangeCheck(length, fromIndex, toIndex) {
if (fromIndex > toIndex) {
console.error("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
console.error(fromIndex);
}
if (toIndex > length) {
console.error(toIndex);
}
}

function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

function dualPivotQuicksort( arr, left, right, div) {
var len = right - left;

if (len < 27) { // insertion sort for tiny array
for (var i = left + 1; i <= right; i++) {
for (var j = i; j > left && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
return;
}
var third = Math.floor(len / div); //TODO: check if we need to round up or down or just nearest

// "medians"
var m1 = left  + third;
var m2 = right - third;

if (m1 <= left) {
m1 = left + 1;
}
if (m2 >= right) {
m2 = right - 1;
}
if (arr[m1] < arr[m2]) {
swap(arr, m1, left);
swap(arr, m2, right);
}
else {
swap(arr, m1, right);
swap(arr, m2, left);
}
// pivots
var pivot1 = arr[left];
var pivot2 = arr[right];

// pointers
var less  = left  + 1;
var great = right - 1;

// sorting
for (var k = less; k <= great; k++) {
if (arr[k] < pivot1) {
swap(arr, k, less++);
}
else if (arr[k] > pivot2) {
while (k < great && arr[great] > pivot2) {
great--;
}
swap(arr, k, great--);

if (arr[k] < pivot1) {
swap(arr, k, less++);
}
}
}
// swaps
var dist = great - less;

if (dist < 13) {
div++;
}
swap(arr, less  - 1, left);
swap(arr, great + 1, right);

// subarrays
dualPivotQuicksort(arr, left,   less - 2, div);
dualPivotQuicksort(arr, great + 2, right, div);

// equal elements
if (dist > len - 13 && pivot1 != pivot2) {
for (var k = less; k <= great; k++) {
if (arr[k] == pivot1) {
swap(arr, k, less++);
}
else if (arr[k] == pivot2) {
swap(arr, k, great--);

if (arr[k] == pivot1) {
swap(arr, k, less++);
}
}
}
}
// subarray
if (pivot1 < pivot2) {
dualPivotQuicksort(arr, less, great, div);
}
}
return dualPivotQS;
}());

/**********************************************************************************************************************/

};

Benchmark.prototype.teardown = function() {
shuffle(arr);
};

</script>
``````

## Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
Quick Sort Due
``````   function quickSortNow(arr){
quick(arr,  0, arr.length - 1);
return arr
};

function partitionNow(arr, left, right) {

var pivot = arr[Math.floor((right + left) / 2)],
i = left,
j = right;

console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right);

while (i <= j) {
while (arr[i] < pivot) {
i++;
console.log('i = ' + i);
}

while (arr[j] > pivot) {
j--;
console.log('j = ' + j);
}

if (i <= j) {
console.log('swap ' + arr[i] + ' with ' + arr[j]);
swapQuickSort(arr, i, j);
i++;
j--;
}
}

return i;
};

function swapQuickSort(arr, index1, index2){
var aux = arr[index1];
arr[index1] = arr[index2];
arr[index2] = aux;
};

function quick(arr, left, right){

var index;

if (arr.length > 1) {

index = partitionNow(arr, left, right);

if (left < index - 1) {
quick(arr, left, index - 1);
}

if (index < right) {
quick(arr, index, right);
}
}
return arr;
};
``````
pending…
Quick Sort Tre
``````    function quicksort(arr, begin, end) {

if (typeof begin == 'undefined') begin = 0
if (typeof end == 'undefined') end = arr.length

if (end - begin < 2) return

var pivot = _quicksortChoosePivot(arr, begin, end)

partition(arr, begin, end, pivot)

quicksort(arr, begin, pivot)
quicksort(arr, pivot + 1, end)

return arr
}

function _quicksortChoosePivot(arr, begin, end) {
return begin //+ Math.floor(Math.random() * (end - begin))
}

Array.prototype.swap = function(index1, index2) {

var tmp = this[index1]

this[index1] = this[index2]
this[index2] = tmp

return this
}

function partition(arr, begin, end, pivot) {

var i = begin,
pivotValue = arr[pivot]

if (pivot != begin) arr.swap(begin, pivot)

for (var j = i; j <= end; j++) {

// If element > pivot do nothing...
if (arr[j] <= pivotValue) {
// swap element with left most element that's bigger than the pivot
arr.swap(i, j)
i++
}
}

arr.swap(begin, i - 1)
}``````
pending…
Flashsort 2
``````                 function flashSort(arr) {
var n = arr.length;
var i = 0, j = 0, k = 0, t;
var m = ~~( n * 0.125 );
var l = [];
var anmin = Math.max.apply(Math, arr);
var nmax = Math.min.apply(Math, arr);
var nmove = 0;

for ( i = 0; i < m; i++ ) {
l[ i ] = 0;
}

if ( anmin == arr[ nmax ]) return;

var c1 = ( m - 1 ) / ( arr[ nmax ] - anmin );

for ( i = 0; i < n; ++i ) {
k = ~~( c1 * ( arr[ i ] - anmin ) );
++l[ k ];
}

for ( k = 1; k < m; ++k ) {
l[ k ] += l[ k - 1 ];
}

var hold = arr[ nmax ];
arr[ nmax ] = arr[ 0 ];
arr[ 0 ] = hold;

var flash;
j = 0;
k = m - 1;
i = n - 1;

while ( nmove < i ) {
while ( j > ( l[ k ] - 1 ) ) {
k = ~~( c1 * ( arr[ ++j ] - anmin ) );
}
flash = arr[ j ];

while ( j != l[ k ] ) {
k = ~~( c1 * ( flash - anmin ) );
hold = arr[ ( t = l[ k ]-1) ];
arr[ t ] = flash;
flash = hold;
--l[ k ];
++nmove;
}
}

for( j = 1; j < n; ++j ) {
hold = arr[ j ];
i = j - 1;
while( i >= 0 && arr[i] > hold ) {
arr[ i + 1 ] = arr[ i-- ];
}
arr[ i + 1 ] = hold;
}
return arr
}
``````
pending…
Flashsort 3
``````function flashSort2(arr) {

var lengthy = arr.length;
var i = 0, j = 0, k = 0, t;

var m = ~~( lengthy * 0.125 );
var left = [];
var anmin = Math.max.apply(Math, arr);
var nmax = Math.min.apply(Math, arr);
var nmove = 0;
var finalSwaps = 0;

while(i < m) {
left[ i ] = 0;
i++
}

if ( anmin == arr[ nmax ]) return;

var c1 = ( m - 1 ) / ( arr[ nmax ] - anmin );

left[0] = lengthy-1;

for ( k = 1; k < m; ++k ) {
left[ k ] += left[ k - 1 ];
}

var hold = arr[ nmax ];
arr[ nmax ] = arr[ 0 ];
arr[ 0 ] = hold;

var flash;
j = 0;
k = m - 1;
i = lengthy - 1;

while ( nmove < i ) {
flash = arr[ 0 ];

while ( j != left[ k ] ) {
k = ~~( c1 * ( flash - anmin ) );
hold = arr[ ( t = left[ k ]-1) ];
arr[ t ] = flash;
flash = hold;
--left[ k ];
++nmove;
}
}

for( j = 1; j < lengthy; ++j ) {

hold = arr[ j ];
i = j - 1;

while( i >= 0 && arr[i] > hold ) {
arr[ i + 1 ] = arr[ i-- ];
}

arr[ i + 1 ] = hold;
}
return arr
}``````
pending…
Flash Sort 1
``````                 function flashSort(arr) {
var n = arr.length;
var i = 0, j = 0, k = 0, t;
var m = ~~( n * 0.125 );
var l = [];
var anmin = arr[ 0 ];
var nmax = 0;
var nmove = 0;

for ( i = 0; i < m; i++ ) {
l[ i ] = 0;
}

for ( i = 1; i < n; ++i ) {
if ( arr[ i ] < anmin ) anmin = arr[ i ];
if ( arr[ i ] > arr[ nmax ] ) nmax = i;
}

if ( anmin == arr[ nmax ]) return;

var c1 = ( m - 1 ) / ( arr[ nmax ] - anmin );

for ( i = 0; i < n; ++i ) {
k = ~~( c1 * ( arr[ i ] - anmin ) );
++l[ k ];
}

for ( k = 1; k < m; ++k ) {
l[ k ] += l[ k - 1 ];
}

var hold = arr[ nmax ];
arr[ nmax ] = arr[ 0 ];
arr[ 0 ] = hold;

var flash;
j = 0;
k = m - 1;
i = n - 1;

while ( nmove < i ) {
while ( j > ( l[ k ] - 1 ) ) {
k = ~~( c1 * ( arr[ ++j ] - anmin ) );
}
flash = arr[ j ];

while ( j != l[ k ] ) {
k = ~~( c1 * ( flash - anmin ) );
hold = arr[ ( t = l[ k ]-1) ];
arr[ t ] = flash;
flash = hold;
--l[ k ];
++nmove;
}
}

for( j = 1; j < n; ++j ) {
hold = arr[ j ];
i = j - 1;
while( i >= 0 && arr[i] > hold ) {
arr[ i + 1 ] = arr[ i-- ];
}
arr[ i + 1 ] = hold;
}
return arr
}
``````
pending…
Quicksort 6 - reverse loop
``````function quickSort(arr) {
if (arr.length <= 1) {
return arr
}
var randomNumber = Math.floor(Math.random()* arr.length)
var pivotNumber = arr.splice(randomNumber, 1)
var left = []
var right = []
var x = arr.length;

while (x--) {

if (arr[x] <= pivotNumber) {
left.push(arr[x])
}
else {
right.push(arr[x])
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}
``````
pending…
Quicksort 7 - median pivot
``````function quickSort(arr) {

if (arr.length <= 1) {
return arr
}

var medianArray = [
arr[0],
arr[Math.floor((arr.length)/2)],
arr[(arr.length)-1]
]

/* here we run a 2 pass bubble sort to find the median number...*/
var temp;
if (medianArray[0] > medianArray[1]) {
temp = medianArray[1]
medianArray[1] = medianArray[0]
medianArray[0] = temp
}
if (medianArray[1] > medianArray[2]) {
temp = medianArray[2]
medianArray[2] = medianArray[1]
medianArray[1] = temp
}

/* now we take the median number and grab the actual value of that
number in our current arr */

median = medianArray[1]
median = arr[median]
var pivotNumber =  arr.splice(median, 1)
var left = []
var right = []
var x = arr.length;

while (x--) {

if (arr[x] <= pivotNumber) {
left.push(arr[x])
}
else {
right.push(arr[x])
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}``````
pending…
Quicksort 8 - assignment instead of push
``````function quickSort(arr) {

if (arr.length <= 1) {
return arr
}

var medianArray = [
arr[0],
arr[Math.floor((arr.length)/2)],
arr[(arr.length)-1]
]

/* here we run a 2 pass bubble sort to find the median number...*/
var temp;
if (medianArray[0] > medianArray[1]) {
temp = medianArray[1]
medianArray[1] = medianArray[0]
medianArray[0] = temp
}
if (medianArray[1] > medianArray[2]) {
temp = medianArray[2]
medianArray[2] = medianArray[1]
medianArray[1] = temp
}

/* now we take the median number and grab the actual value of that
number in our current arr */

median = medianArray[1]
median = arr[median]
var pivotNumber =  arr.splice(median, 1)
var left = []
var right = []
var x = arr.length;

while (x--) {

if (arr[x] <= pivotNumber) {
left[left.length] = arr[x]
}
else {
right[right.length] = arr[x]
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}``````
pending…
Default Recursive Javascript Quicksort
``StandardRecursiveQuicksort.sort(arr);``
pending…
Three Way Partition Javascript Quicksort
``ThreeWayPartitionQuicksort.sort(arr);``
pending…
Dual Pivot Javascript Quicksort
``DualPivotQuicksort.sort(arr);``
pending…
Default Javascript Sort
``arr.sort(function(a, b){return a-b});``
pending…
Quicksort 5
``````function quickSort(arr) {
if (arr.length <= 1) {
return arr
}
var randomNumber = Math.floor(Math.random()* arr.length)
var pivotNumber = arr.splice(randomNumber, 1)
var left = []
var right = []

for (var x=0;x<arr.length;x++) {
if (arr[x] <= pivotNumber) {
left.push(arr[x])
}
else {
right.push(arr[x])
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}
``````
pending…

## Revisions

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