Quick Sort

by ktstowell

JavaScript

var runs = [1000, 10000, 100000, 500000, 1000000];

function create(ln) {
	var src = [];
	var max = 10000;
  
  for(var i = 0; i<ln; i++) {
    src.push(Math.round(Math.random() * max));
  }
  
  return src;
}

function run(length) {
  var started;
	var finished;
	var elapsed;
  var src = create(length);
  
  if(!length) { return; }
  
  report('Running Quick Sort on ' + length + ' elements.');
  started = Date.now();
  sorted = sort(src);
  finished = Date.now();
  elapsed = (finished - started) / 1000;
  
  report('Finished in: ' + elapsed +' seconds.', true);
  
  console.log(sorted)
 	return sorted;
}

function report(msg, br) {
	var div = document.createElement('div');
  div.textContent = msg;
  document.body.appendChild(div);
  
  if(br) {
  	br = document.createElement('br');
    document.body.appendChild(br);
  }
}

function sort(arr) {
	var lt = [];
  var gt = [];
  var pivot = arr[0];
  
  if(!arr || !arr.length) {
  	return [];
  }
   
  for(var i = 1; i< arr.length; i++) {
  	if(arr[i] < pivot) { lt.push(arr[i]); }
    	else { gt.push(arr[i]); }
  }
  
  return sort(lt).concat(pivot, sort(gt));
}

report('Running quick sort on: [' + runs.join(', ') + ']', true);

(function runner(inc) {
	run(runs[inc]);
	
  inc += 1;
  
  setTimeout(function() {
    if(runs[inc]) {
      runner(inc);
    }
  }, 1000);
})(0);