Sort stack using another stack

Question

I want to know the time complexity of this algorithm, which is used to sort a stack using another stack. I thought it was O (N ^ 2), but apparently it looks more than.

public static Stack<Integer> sort(Stack<Integer> s) { Stack<Integer> r = new Stack<Integer>(); while(!s.isEmpty()) { int tmp = s.pop(); while(!r.isEmpty() && r.peek() > tmp) { s.push(r.pop()); } r.push(tmp); } return r; } 

Answer 1

If the sort stack [x_2, .., x_n] (the stack grows to the right) takes time t(n-1) , the sort time [x_1, .., x_n] will do the following

• Sort substack [x_2, .., x_n] of s
• Pop x_1 to tmp
• Transfer no more than n-1 elements from r to s
• Press x_1 to r
• Process the elements listed in step 3 again, but they are in such a way that the inner while loop never starts.

Thus, running the algorithm on [x_1, .., x_n] will take no more than t(n-1) + O(n) . This leads to (for some constant c )

 t(n) <= O(n) + t(n-1) <= c * n + t(n-1) t(n) <= c * n + c * (n - 1) + t(n-2) <= ... <= c * (1 + 2 + ... + n) t(n) <= c * n(n + 1) / 2 

So t(n) is O(n^2) .

Answer 2

Looks O (n ^ 2) to me. I assume that an already sorted stack has the worst performance. I counted the number of times s.push is executed, given an already sorted stack of a certain size.

 Stack of size 1. backpushes: 0 Stack of size 2. backpushes: 1 Stack of size 3. backpushes: 3 Stack of size 4. backpushes: 6 Stack of size 5. backpushes: 10 Stack of size 6. backpushes: 15 Stack of size 7. backpushes: 21 Stack of size 8. backpushes: 28 Stack of size 9. backpushes: 36 

0,1,3,6,10 is a sequence of triangular numbers . For a sorted stack of size N, a (N ^ 2 + N) / 2 backward stroke is required. This makes it O (N ^ 2).

Answer 3

This problem can be solved in complexity o (n ^ 2). This can be done without using the largest pop-up and keeping the rest elements in the second stack and updating the size of the first stack, and then dropping back to the first stack. look at the code snippet.

  #include<stdio.h> func(struct stack *s1) { struct stack* s2=(struct stack*) malloc(sizeof(struct stack)) int i=0; int max=INT_MIN; size=s1->size; if(s1->size==0) { return; } for(;i<size;i++) { while(size(s1)!=size)//popping the elements and pushing in s2 stack and keeping track of maximum element. { temp=pop(s1); if(temp>max) { push(s2,max); max=temp; } } push(s1,max);//pushing the max element into stack s1 back and updating the size in push operation. while(!empty(s2))//pushing extracted numbers back into stack s1 from s2. { push(s1,pop(s2)); } } }