sorting elements of stack using javascript
I m trying to understand sorting a stack elements using recursion given in http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S:
is_empty(S) : Tests whether stack is empty or not.
push(S) : Adds new element to the stack.
pop(S) : Removes top element from the stack.
top(S) : Returns value of the top element. Note that this function does not remove element from the stack. I tried below but getting error
var stack = [-3, 14, 18, -5, 30];
function sortStack() {
if (stack.length > 0) {
temp = stack.pop();
sortStack();
sortedInsert(temp, stack);
}
}
function sortedInsert(element, stack) {
if (stack.length > 0 || element > stack[stack.length - 1]) {
stack.push(element);
} else {
temp = stack.pop();
sortedInsert(element, stack);
stack.push(temp);
}
}
sortStack();
console.log(stack);With javascript, local (scoped) variables need to be declared as var, otherwise they are static. Without the var before t in sortStack(), t would be a static and just get overwritten with each pop, leaving t == -3 on all the returns from sortStack(). The same issue occurs with x in sortedInsert().
var stack = [-3, 14, 18, -5, 30];
function sortStack(s) {
if (s.length > 0) {
var t = s.pop();
sortStack(s);
sortedInsert(s, t);
}
}
function sortedInsert(s, e) {
if (s.length == 0 || e > s[s.length - 1]) {
s.push(e);
} else {
var x = s.pop();
sortedInsert(s, e);
s.push(x);
}
}
sortStack(stack);
console.log(stack); If you just want to sort the array, you can use sort() method. Check example below:
var stack = [-3, 14, 18, -5, 30];
console.log(stack.sort());
If you want to understand how to sort array manually, have a look at this ans (Note: below code is copied from same ans):
var stack = [-3, 14, 18, -5, 30];
function arrSort(arr, subkey) {
//Default to 0 if no subkey is set
subkey = (subkey === undefined ? 0 : subkey);
var a = arr.slice(0),
b = [], x;
// For each section in the array, create an array containing whatever we are trying to sort by and our unique ID
for (x in a) {
b[x] = [a[x][subkey], x];
}
b = b.sort();
//Wipe out all the data that's currently in arr!
arr.splice(0, arr.length);
for (x in b) {
arr.push(a[b[x][1]]);
}
return arr;
}
// console.log(arrSort(stack, 0));
console.log(arrSort(stack));
var stack = [-3, 14, 18, -5, 30];
function compare(a,b) {
return parseInt(a, 10) - parseInt(b, 10);
}
stack.sort(compare);
console.log(stack);
上一篇: R闪亮（仅替代文字）