# Sort stack in ascending order

Posted on

Problem

I am using two more helper stacks to sort. Kindly suggest improvements in terms of space and time.

import java.util.ArrayDeque;
import java.util.Deque;

public class SortStackAscendingOrder {

Deque<Integer> stackhelper1 = new ArrayDeque<>();
Deque<Integer> stackHelper2 = new ArrayDeque<>();

public Deque<Integer> sortStack(Deque<Integer> mainStack) {
if (mainStack.isEmpty()) {
return null;
}

while (!mainStack.isEmpty()) {
int mainItem = mainStack.pop();
int helperItem1 = -1;
if (!stackhelper1.isEmpty()) {
helperItem1 = stackhelper1.peek();
}
if (mainItem > helperItem1) {
// push all helperItem1 to helperItem2, till it is in ascending
// order
while (!stackhelper1.isEmpty() && mainItem > helperItem1) {
stackHelper2.push(stackhelper1.pop());
helperItem1 = stackhelper1.peek();
}
// push mainItem.
stackhelper1.push(mainItem);
// bring back all the helperItem2
while (!stackHelper2.isEmpty()) {
stackhelper1.push(stackHelper2.pop());
}
} else {
// directly push in stackhelper1
stackhelper1.push(mainItem);
}
}

return stackhelper1;

}

}

Solution

Possible bug:

The following demo will throw a NullPointerException:

public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();

System.out.println("Original stack: " + stack);
SortStackAscendingOrder sorter = new SortStackAscendingOrder();

Deque<Integer> sortedStack = sorter.sortStack(stack);

System.out.println("Sorted original stack: " + sortedStack);

stack.clear();

System.out.println("Another stack: " +
sorter.sortStack(stack));

System.out.println("Sorted original stack again: " + sortedStack);
}

Most likely the problem above is due to the fact that you return stackhelper1, which is an essential internal facility in your algorithm.

API design:

First of all, I would consider implementing the stack sort as a static method that does not “leak” any internals. The idea here is that you sort the input stack: just like sorting methods in java.util.Arrays, all are void and modify the input arrays instead of returning a sorted copy.

All in all, I had this in mind:

public static void sortStack(Deque<Integer> mainStack) {
Deque<Integer> stackHelper1 = new ArrayDeque<>();
Deque<Integer> stackHelper2 = new ArrayDeque<>();

while (!mainStack.isEmpty()) {
int mainItem = mainStack.pop();
int helperItem1 = -1;

if (!stackHelper1.isEmpty()) {
helperItem1 = stackHelper1.peek();
}

if (mainItem > helperItem1) {
while (!stackHelper1.isEmpty() && mainItem > helperItem1) {
stackHelper2.push(stackHelper1.pop());
helperItem1 = stackHelper1.peek();
}

stackHelper1.push(mainItem);

while (!stackHelper2.isEmpty()) {
stackHelper1.push(stackHelper2.pop());
}
} else {
stackHelper1.push(mainItem);
}
}

mainStack.clear();
}

You should take more attention to the naming convention of Java :

Deque<Integer> stackhelper1 = new ArrayDeque<>();
Deque<Integer> stackHelper2 = new ArrayDeque<>();

The variable should be named stackHelper1, the H is what was missing. I don’t like numbered variable names. It always let me wonder if it’s a bad design decision or simply bad names. In this case, I think it’s just a bad name, maybe try to really name it after what they are.

// push mainItem.
stackhelper1.push(mainItem);

You really don’t have to state the obvious in a comment. Just by reading the line of code I can easily understand that you’re pushing mainItem`, that’s what the method is called. Almost all your comments are noise in the code. What would have a been a bit more useful is Javadoc to explain what the method is about and maybe expose your “algo”, something like this javadoc.

if (mainStack.isEmpty()) {
return null;
}

I would have really like to have been warned that using your method with an empty collection would return me null. If I passe you an empty collection, I would have expected to have an empty collection in return. Returning null just expose the user of the method to NullPointerExceptions. You should really ask yourself if returning null is a good thing, in a good number of occasion it will complicate things.

The null pointer exception pointed earlier can be avoided if you just do a check stackhelper1.isEmpty()

if(!stackhelper1.isEmpty())
helperItem1 = stackhelper1.peek();

In terms of improving space complexity, there is a way to sort stack using one stack:-

private static Stack<Integer> sortWithOneStack(Stack<Integer> s1) {
Stack<Integer> s2 = new Stack<Integer>();
while(!s1.isEmpty()){
int topEl = s1.pop();
while(!s2.isEmpty() && s2.peek() > topEl){
s1.push(s2.pop());
}
s2.push(topEl);
}
return s2;
}

You just push the element back to the original stack if that is less than the top of the other stack.

In fact, there is a way to do it without using any external stack at all. Here is the code for it.

public static void sort(Stack<Integer> st){
if(st.isEmpty())
return;
int el = st.pop();
sort(st);
putInSortedOrder(st,el);
}

private static void putInSortedOrder(Stack<Integer> st, int el) {
if(st.isEmpty() || st.peek() < el){