compare-shuffling-algorythms.js

const calculateAverage = array => array.reduce((sum, value) => sum + value, 0) / array.length;

const calculateStandardDeviation = values => {
  const average = calculateAverage(values);
  const squareDiffs = values.map(value => (value - average) ** 2);
  return Math.sqrt(calculateAverage(squareDiffs));
}

const testShuffler = shuffler => {
  const array = [1, 2, 3];
  const rounds = 1000000;

  let count = {};

  let startCounter = Date.now();

  for (let i = 0; i < rounds; i++) {
    let sorted = shuffler(array);
    let prop = sorted.join('');
    count[prop] = (count[prop] || 0) + 1;
  }

  const values = Object.values(count);
  const average = calculateAverage(values);
  const delta = values.map(value => value / average);
  
  return {
    name: shuffler.name,
    standardDeviation: calculateStandardDeviation(delta),
    duration: Date.now() - startCounter
  };
}

const testMultipleShufflers = shufflers => shufflers.map(testShuffler);

// Defining shufflers
const randomSortingShuffle = array => [ ...array ].sort(() => Math.random() > 0.5);

const fisherYatesShuffle = array => {
  let currentIndex = array.length;
  let temporaryValue;
  let randomIndex;
  while (currentIndex !== 0) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex--;
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
  return array;
}

const fisherYatesInvertedShuffle = array => {
  for (let index = 0; index < array.length; index++) {
    randomIndex = Math.floor(Math.random() * (index + 1));
    let temporaryValue = array[index];
    array[index] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
  return array;
}

const multiple = testMultipleShufflers([
  randomSortingShuffle,
  fisherYatesShuffle,
  fisherYatesInvertedShuffle
]);

console.log(multiple);

// Test in repl, at https://repl.it/@josecarneiro/compare-sorting-algorythms