Informatik-Unterricht: Zählen der Vergleichsoperationen beim Sortieren eines Arrays

count-compare-operations.js

// $ node count-compare-operations.js > abc.txt
// $ R
// > plot(read.table("abc.txt"))

function generate_ints(n) {
  var arr = [];
  while (n--) {
    arr.push(Math.floor(Math.random()*1000));
  }
  return arr;
}

function main () {
  var n = 10;
  while (n < 500000) {
    n = Math.floor(n*1.5);
    var arr = generate_ints(n);
    var cmpOperations = 0;
    arr.sort(function (a, b) {
      cmpOperations++;
      if (a < b) return -1;
      if (a === b) return 0;
      return 1;
    });
    console.log(n + ' ' + cmpOperations);
  }
}

main();