0

I am trying to write a code for sorting a stack without using extra space. It is logically correct but my output is completely random. Could someone point out my mistake?

void insertatsortstack(int element, stack<int> s){

    if(s.empty()==1 || element > s.top())
    {
        s.push(element);
        return;
    }

    int temp=s.top();
    s.pop();
    insertatsortstack(element,s);
    s.push(temp);
}

void sortstack(stack<int> s){
    if(s.size()>0){
        int element=s.top();
        s.pop();
        sortstack(s);
        insertatsortstack(element,s);
    }
}
Romeo Sierra
  • 1,666
  • 1
  • 17
  • 35
user46562
  • 31
  • 9
  • 1
    The indentation seems to be also random, so it is hard to read… Have you tried Valgrind or so? If result is random, I suspect some memory corruption. – v6ak May 30 '18 at 05:17
  • 2
    `it is logically correct but my output is completely random` ... isn't this a complete contradiction? Do you really have a real world need to do this, or is this a homework problem? My vote is to _not_ use the stack to sort. Instead, pop into a data structure like an array, which is much easier to use for sorting. Then, reload the stack afterwards. – Tim Biegeleisen May 30 '18 at 05:25
  • when i made a dry run according to me its correct and yes its not a homework problem . I am solving question from gfg to learn in detail and make it useful for my upcoming placement – user46562 May 30 '18 at 05:48
  • @user46562 I have made some edits to make it more readable. Can you accept those? – Romeo Sierra May 30 '18 at 05:50
  • Okay good! Now, to the algorithm, the given part of your algorithm works fine. I have assumed the rest of the implementation without changing this part of the algorithm. And it works all fine. I would suggest you to check your implementation of the rest of the parts, specially, `stack`. If there are flaws that you are experiencing, they could most probably be caused by this. – Romeo Sierra May 30 '18 at 07:49
  • 1
    On a sidenote, you said that you implement this to not to use extra space, but I think you have failed. Because, since you are using recursion, you have ended up consuming a lot of space in the runtime stack... – Romeo Sierra May 30 '18 at 07:52
  • 1
    Try writing down, *in English*, what you want your code to do. Step by step. Using a deck of cards or a stack of coins, simulate those steps by hand. *Then* write code to implement that solution on the computer. – Jim Mischel May 30 '18 at 14:39

2 Answers2

0

I think you are coming from the Java background. You are passing the value in functions which will make a copy of your stack and your original stack will not be changed. You need to pass value by the reference.

void insertatsortstack(int element, stack<int> & s);
void sortstack(stack<int> &s);

Working Code Implementation

(Assuming that you are using std:: stack)

Community
  • 1
  • 1
RATHI
  • 5,129
  • 8
  • 39
  • 48
-1

#include<bits/stdc++.h> using namespace std;

void insertatsortstack (int element, stack < int >&s) {

if (s.empty () == 1 || element > s.top ())

{

s.push (element);

return;

}

int temp = s.top ();

s.pop ();

insertatsortstack (element, s);

s.push (temp);

}

void

sortstack (stack < int >&s) {

if (s.size () > 0) {

int element = s.top ();

s.pop ();

sortstack (s);

insertatsortstack (element, s);

}

}

int

main () {

stack < int >s;

s.push (5);

s.push (1);

s.push (4);

s.push (3);

s.push (6);

s.push (9);

s.push (2);

s.push (3);

s.push (8);

sortstack (s);

while (s.empty () == false) {

cout << s.top () << " ";

s.pop ();

}

}

jaydeep singh
  • 1