Stack is sorted with O(N)

Question

I'm creating a method to test if a given stack is sorted or not. I've completed the main task of the program but is there a way to implement this algorithm without having O(N^2). I would like to get this one with O(N). Does such a solution exist? If so can someone point me in the right direction.

Some rules - Only one auxiliary stack can be made. - No additional data structures. - If a stack is empty or has one item it is assumed to be sorted. - Must perform in O(N)

public static boolean isSorted(Stack s){ boolean sorted = true; Stack backup = new Stack(); int prev, curr; if(s.isEmpty() || s.size() == 1) { sorted = true; } else { while(!s.isEmpty()){ prev = s.pop(); backup.push(prev); curr = s.pop(); backup.push(curr); if(prev > curr && sorted) sorted = false; } } while(!backup.isEmpty()) { s.push(backup.pop()); } return sorted; }

Sample Input: {20,20,17,11,9,8,3,2}

Output:

 top 2 3 8 9 11 17 20 20 bottom | isSorted = true | top 2 3 8 9 11 17 20 20 bottom

At the end of the function. The stack given should be in its original state. I just have to get this in O(N)

Subclass Stack, override push to flip a flag from sorted to unsorted if it sees a value out of line. No computation required after that. O(1) after all those little comparison costs are amortized in. — tadman
– tadman, Commented Mar 9, 2017 at 4:24
Not my downvote, but can't you just pop each item off the stack and make sure everything is in sequence? — Tim Biegeleisen
– Tim Biegeleisen, Commented Mar 9, 2017 at 4:25
@TimBiegeleisen I am popping the values and making sure everything is in sequence, as well pushing everything into a backup stack. Then finally pushing everything back into the original stack. — Dilawer
– Dilawer, Commented Mar 9, 2017 at 4:27
You can do it with a recursive function, this avoids the additional popping and you can switch the original stack with the backup stack, but I guess that depends on the definition of O if it would be linear in time (certainly not space) — eckes
– eckes, Commented Mar 9, 2017 at 4:28
@eckes Perhaps my understanding of BigO is frickle. I recently started learning about it. Thank you for the clarification. I shall find a way to fix that bug, thank you :) — Dilawer
– Dilawer, Commented Mar 9, 2017 at 4:35

Mureinik · Accepted Answer · 2017-03-09 04:53:44Z

The concept you're presenting here is not O(n²), but indeed O(n) - for each element of the stack you perform a constant number of operations, regardless of the size of N.

You should note, however, that you have a bug there - on each iteration of the loop you pop two elements and compare them, so you're effectively testing only if each pair of elements is sorted, not the entire set (e.g., try this algorithm with the values {2, 1, 500, 400}). Additionally, note that consecutive equal values don't break sorting, so you should use >= instead of >. Another optimization could be to fail fast once you detect the stack is unsorted:

public static boolean isSorted(Stack s) { boolean sorted = true; Stack backup = new Stack(); int prev; int curr = Integer.MIN_VALUE; while (!s.isEmpty() && sorted) { prev = curr; curr = s.pop(); backup.push(curr); sorted = (prev <= curr); } while (!backup.isEmpty()) { s.push(backup.pop()); } return sorted; }

Thank you! @eckes made me aware of my running time. It makes more sense to me. Also thank you for making me understand my bug. So If I were to encounter an out of order stack in the first half, I would simply stop searching further and push back all the items from backup. That makes it more efficient, regardless of whether it's worse case is O(N) in my case. Appreciate it!
In retrospect, the initial size check is redundant - I'll remove it.

Collectives™ on Stack Overflow

Stack is sorted with O(N)

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related