Sorting numbers on the stack using a single int variable

Terribly inefficient, but follows the rules :)

Stack<Integer> s=new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);

int a = -1;
while (a == -1) { // Here 'a' is used as a kind of boolean that tells us whether we need to keep checking for items to reorder or not.
    for (a = 0; a < s.size() - 1; a++) { // Now 'a' becomes stack element index.
        if (s.get(a) > s.get(a + 1)) {
            a = s.remove(a); // Here 'a' again changes meaning and holds the value that needs to be reordered.
            s.push(a);
            a = -1; // And here, 'a' is back to being used as a kind of boolean flag to control the outer loop.
            break;
        }
    }
}

      

        
        
        
      

    

EDIT : Basically, I am using the fact that I know Stack

extends Vector

. Therefore, I do not need to use only the standard methods Pop

and Push

to access / delete items. I can use the usual methods List

.

And then I just squeeze the best possible use a

by using it for different purposes at different times (exit flag, loop index, temporary storage to override the value). Usually very bad programming practice.

So the algorithm is basically that I go through the Stack elements. Every time I find an element that is larger than the next one, I remove it and then push it to the end of the stack. At this point, I will stop the loop and reset a

to -1

to make sure I start the loop again. I keep doing this until I can loop through all the elements of the stack without having to reorder anything.

EDIT 2 : Here's another alternative that is a little harder to read but still follows the rules and works better after the bubble sort pattern. The principles used are pretty much the same as my first attempt (abuse Stack

like List

+ using a variable a

for multiple uses).

Stack<Integer> s=new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);

int a = -1;
while (a < 0) { // keep looping if the previous loop performed at least one swap.
    a = 0;

    // if 'a' is >= 0, then it simply holds the index.
    // if 'a' < 0, then the index can be obtained by applying the bitwise complement operator.
    while ((a < 0 ? ~a : a) < (s.size() - 1)) { // loop all items except the last one.
        if (s.get(a < 0 ? ~a : a) > s.get((a < 0 ? ~a : a) + 1)) { // if this item is greater than the next, a swap is needed.
            s.insertElementAt(s.remove(a < 0 ? ~a : a), (a < 0 ? ~a : a) + 1); // swap this value with the next.

            // If this was not done already, flag the fact that a swap was performed by
            // applying the bitwise complement operator to 'a'.
            // This serves as a flag to let the outer loop know
            // that we'll need to perform the stack loop again.
            if (a >= 0) {
                a = ~a;
            }
        }

        // increment index. Or if the bitwise complement operator was applied,
        // then go the opposite way since the value is now negative.
        if (a >= 0) {
            a++;
        } else {
            a--;
        }
    }
}

      

        
        
        
      

    

EDIT 3: Revised my last algorithm to use the bitwise complement operator instead of Math.abs()

.

Also, I would like to point out that, unlike some other clever attempts, this algorithm has no limitations. It won't suffer from StackOverflowException

too many recursive calls because no recursion is used. The memory used is stable. And you can have any value int

in Stack

, even negative ones, and it will work just fine.