Stack Sort

by sym3tri

HTML

<div id="output"></div>

JavaScript

function print(msg) {
  document.getElementById('output').innerHTML += msg + '<br>';
}

function Stack() {
    this.items_ = [];
};
Stack.prototype.push = function(i) {
    this.items_.push(i);
};
Stack.prototype.pop = function() {
    return this.items_.pop();
};
Stack.prototype.peek = function() {
    return this.items_[this.items_.length-1];
};
Stack.prototype.isEmpty = function() {
    return this.items_.length === 0;
};
Stack.prototype.toString = function() {
    return this.items_.toString();
};

function stackSort(s1) {
  var s2 = new Stack(),
    sorted = true,
    current;

  print('start: ' + s1);
  current = s1.pop();
  while (!s1.isEmpty()) {
    if (current >= s1.peek()) {
      s2.push(current);
      current = s1.pop();
    } else {
      s2.push(s1.pop());
      sorted = false;
    }
  }
  s2.push(current);
  print('finish: ' + s2);
  // reverse
  while (!s2.isEmpty()) {
    s1.push(s2.pop());
  }
  if (sorted) {
    return s1;
  } else {
    return stackSort(s1);
  }
}

var s = new Stack();
for (var i = 0; i <= 10; i++) {
  s.push(Math.floor(Math.random() * 10));
}

print('<b>starting stack</b>: ' + s);
print('');
print('<br><b>final result</b>: ' + stackSort(s));